2

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!!!

ptk1113
  • 25
  • 3
  • 1
    The sum of the primes <= 2000000 needs more than 32 bits (2^37 < sum < 2^38) to be represented. Check your `LONG_MAX` (in ``). – pmg Jan 17 '21 at 16:59
  • It seems to me my LONG_MAX is okey :9223372036854775807, but thanks i have never checked these values before. – ptk1113 Jan 17 '21 at 17:24
  • There is a much efficient algorithm wait 10 min I'll give you the code – Mohak Gupta Jan 17 '21 at 17:27
  • No question is asked in the post. You do not state what output the program gives or what output you expect instead. Please read about [how to ask a question](https://stackoverflow.com/help/how-to-ask) and about providing a [mre]. – Eric Postpischil Jan 17 '21 at 17:45
  • `numbers[0]` is used without having been assigned a value. `numbers[1]` is set to `true` even though `1` is not a prime number. – pmg Jan 17 '21 at 17:52
  • 1
    instead of marking the numbers as prime, use `calloc` to allocate zeroed memory (false) and mark numbers as *composite* by setting them to `true`. Then count all the falses. Simpler code. Also, you can just initialize sum with 2 and skip every even number as they will be composite anyway. Finally, compile with optimizations enabled. Only long long is guaranteed to have enough precision on windows – Antti Haapala -- Слава Україні Jan 17 '21 at 19:16

2 Answers2

2

The problem in your code is you do not use the correct printf conversion specifier for sum that has type unsigned long: you should write:

printf("%lu\n", sum);

The result, 142913828923 exceeds the range of 32-bit integers, so you should actually use a larger type such as long long which is guaranteed to have at least 63 value bits. The last loop should start from 2 to avoid counting 1 as a prime number.

Here is a modified version with some improvements:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int main() {
    int limit = 2000000;
    bool *numbers = (bool *)malloc(sizeof(bool) * limit);
    if (numbers == NULL) {
        printf("not enough memory\n");
        return 1;
    }
    for (int run = 0; run < limit; run++) {
        numbers[run] = true;
    }
    for (long long i = 2; i * i < limit; i++) {
        if (numbers[i] == true) {
            for (long long x = i * i; x < limit; x += i) {
                numbers[x] = false;
            }
        }
    }
    long long sum = 0;
    for (int run = 2; run < limit; run++) {
        if (numbers[run] == true) {
            sum = sum + run;
        }
    }
    printf("%lld\n", sum);
    free(numbers);
    return 0;
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
-2

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.
dawg
  • 98,345
  • 23
  • 131
  • 206