Printing 64 bit prime sums

Question

#include<stdio.h>
int main(){
    int n,k=1;
    int i,j;
    unsigned long long int sum=0;
    scanf("%d",&n);
    for(i=2;i<n;i++){
        for(j=2;j<=i;j++){
            if(i%j==0)
                k++;
        }
        if(k==2){
            sum=sum+i;
        }
        k=1;
    }
    printf("%lld",sum);
    return 0;
}

This code is working fine for input 1000,10000 but not for 100000,1000000, I mean it prints nothing. I have also tried %I64d but no use.
How can I print sum ?

Answer 1

I suggest you print the sum at each iteration instead of just at the end, so you can see the progress of the computation. Besides being easier to debug your printf statement, you can then also detect a possible wrap around (if unsigned long long is not enough for the sum, for example).

Anyway -- I think your question is actually related to your printf format string: use %llu instead of %lld. See the code below:

int main(){
    int n,k=1;
    int i,j;
    unsigned long long int sum=0;
    scanf("%d",&n);
    for(i=2;i<n;i++){
        for(j=2;j<=i;j++){
            if(i%j==0)
                k++;
        }
        if(k==2){
            sum=sum+i;
        }
        k=1;
        /* This helps you see what's going on: */
        printf("sum is %llu\n",sum);
    }
    printf("%llu",sum);
    return 0;
}

I have used %llu instead of %lld, and it works fine. If I change it back to %lld, nothing is printed on each iteration.

And see that your input (n) may not exceed the maximum size of int on your platform. (But the sum may be larger, since you declared it as unsigned long long).

Also, when checking for primes, you can do some basic optimizations:

• The only even number you need to check is 2. All other primes are odd.
• You don't need to check farther than up to the square root of n. Or, equivalently: suppose you are testing if k divides n. If n/k<k (or if k*k>n), you may stop testing.

Also, you may use the standard boolean type that is available in C.

See the comments in the code below.

#include<stdio.h>
#include<math.h>
/* stdbool defines the type "bool", which can be "true" or "false": */
#include<stdbool.h>

int main(){
    int n;
    int i,j;

    /* prime is initialized to true, since we presume every number is prime
       until we find a divisor for it */
    bool prime = true;

    /* sum is initialized to zero. */
    unsigned long long int sum=0;

    scanf("%d",&n);

    /* If n=2, the result is zero. But if it's greater than two, we need
       to count 2 and start searching from 3. It's easier this way, because then
       we can use i=i+2 in the for loop. */
    if (n>2)
        sum = 2;

    /* no need to count from 2. We start from 3 and count every two numbers. */           
    for(i=3;i<n;i=i+2){
        /* same here. And, since this is the divisor we're looking for, we only 
           need to go up to sqrt(i). We use the long casting here because checking
           j*j<=i would not fit in an int type if j^2 is greater than the maximum
           int. This is a corner case, that happens for example when i is maxint
           (j-1)^2 is below and and j^2 is above it. */
        for(j=3;(long)j*j<=i;j=j+2)
            if(i%j==0) {
                prime = false;
                /* get out, since we already know that this one is composite! */
                break;
            }

        /* no divisors? add it to sum! */
        if (prime)
            sum = sum + i;

        /* reset prime to true, we'll start again with next i */
        prime = true;

        printf("sum is %llu\n",sum);
    }
    printf("%llu\n",sum);
    return 0;
}

These are the reasonably simple optimizations that you can do. There are others, and if you are interested, you can study the sieve of Erathostenes or (if you are math inclined), the Miller-Rabin test (which is not deterministic, but may be of interest). The C library GMP has Miller-Rabin available if you want to use it.