csumprimeseulerr

Euler 10, Sum of primes to 2000000


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 is 2 + 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!!!


Solution

  • 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:

    1. Use a 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 types
    2. Make sure the printf type and length specifiers are correct given the data types being printed.