I have a problem with my algorithm. I can't find where a go wrong in the task below.
Description:
The sum of the primes below
10
is2 + 3 + 5 + 7 = 17
. Find the sum of all the primes below two million.
Here is my solution in C:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int main() {
bool *numbers = (bool *)malloc(sizeof(bool) * 2000000);
unsigned long run = 1;
while (run < 2000000) {
numbers[run] = true;
run++;
}
unsigned long sum = 0;
for (long i = 2; i < 2000000; i++) {
if (numbers[i] == true) {
for (long x = 2 * i; x < 2000000; x += i) {
numbers[x] = false;
}
}
}
run = 0;
while (run < 2000000) {
if (numbers[run] == true) {
sum = sum + run;
}
run++;
}
printf("%d\n", sum-1); // cause 1
free(numbers);
return 0;
}
Thanks for help!!!
You can try something along these lines:
#include <stdio.h>
#include <stdlib.h>
int main(){
unsigned long int i,j;
unsigned long long sum=0; // the sum is potentially large
unsigned long cnt=0;
int limit=2000000; // the limit for the sums
char *primes; // only needs to be used as a flag holder
primes = malloc(sizeof(char)*limit); // flag of is prime or not
if(primes==NULL) {
perror("main, malloc");
return(-1);
} // else
for (i=2;i<limit;i++) // set the flags to True to start
primes[i]=1;
for (i=2;i<limit;i++) // now go through all combos
if (primes[i]) // already know; no need
for (j=i;i*j<limit;j++) // has i and j as factors
primes[i*j]=0; // not prime
for (i=2;i<limit;i++) // now add them up
if (primes[i]) {
sum+=i;
cnt++;
}
// report what was found; note %lu for long or %llu for long long
printf("There are %lu primes less than %d with a sum of %llu",
cnt, limit, sum);
return 0;
}
You can also invert the search to flag composite numbers rather than primes by using calloc
vs malloc
and save a loop (Thanks to Anti Haapala):
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int main(){
unsigned long i,j;
unsigned long long sum=0; // the sum is potentially large
unsigned long cnt=0;
int limit=2000000; // the limit for the sums
bool * composite = (bool *)calloc(limit, sizeof(bool));
if(composite==NULL) {
perror("main, calloc");
return(-1);
}
for (i=2;i<limit;i++) // now go through all combos
if (!composite[i])
for (j=i;i*j<limit;j++) // has i and j as factors
composite[i*j]=true; // composite; not prime
for (i=2;i<limit;i++) // now add them up
if (!composite[i]) {
sum+=i;
cnt++;
}
// report what was found; note %lu for long
printf("There are %lu primes less than %d with a sum of %llu",
cnt, limit, sum);
return 0;
}
Both print:
There are 148933 primes less than 2000000 with a sum of 142913828922
Note:
long long
for the sum which is guaranteed to be 64 bits. While a long may be 32 or 64 bits and an int
may be as short as 16 bits. See C data typesprintf
type and length specifiers are correct given the data types being printed.