Sieve of Eratosthenes
sieve-of-eratosthenes
#include <stdbool.h> // bool
#include <stdio.h> // printf
#include <string.h> // memset
int main(int argc, char* argv[]) {
int limit = 10000;
int calculate = limit * 20;
// Create an array and set all to true
bool numbers[calculate];
memset(&numbers, true, sizeof(bool) * calculate);
// Loop through all the numbers
for (int i = 2; i < calculate; i++) {
// Already crossed out numbers don't have to be checked
if (numbers[i]) {
// Cross out all the numbers that can't be a prime, which are multiples of itself
for (int j = i * i; j < calculate; j += i) {
numbers[j] = false;
}
// Once you exceed the calculate range, you can exit the loop
if (i * i > calculate) {
break;
}
}
}
int sum = 0;
int counter = 1;
// Get the sum of the first 10000 primes
for (int i = 2; i < calculate; i++) {
if (numbers[i]) {
sum += i;
if (counter >= limit) {
break;
}
counter++;
}
}
printf("sum of first %d primes is: %d\n", counter, sum);
return 0;
}