Number too big for int64_t?

Hi guys! I'm getting some troubles trying to find the sum of all primes below 1 million. I think I created a fairly good program (or at least one that should get the job done!), but apparently I'm having trouble with how I declare my variable/variables. This is the code:

Code:

---


/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

 Find the sum of all the primes below one million.*/

#include<stdio.h>
#include<stdint.h>
#include<math.h>

#define MAX 1000000

int isPrime(int64_t a);

int main(int argc[], char *argv[]) {
    int64_t i;
    uintmax_t sum=0;

    for (i=2; i<MAX; i++) {
        if (isPrime(i)==0) {
            sum += i;
            printf("&#37;lld\t", sum);
            printf("%lld\n", i);
        }
    }
   
    printf("%lld", sum);
    printf("Press a key to continue...\n");
    getch();   

    return (0);
}

int isPrime(int64_t a) {
    int64_t i;
   
    if(a%2==0&& a!=2){
        return(1);
    }
   
    for(i=2; i<a/2 ; i++) {
        if(a%i==0) {
            return(1);
        }
    }

    return (0);
}

---

I tried to google some snippets of code, looking for variables and types capable of storing huge numbers, and uintmax_t and int64_t (both declared in stdint.h) were the biggest I found. Any way I can solve this or is this bruteforce method flawed?


edit: Oh yeah, I actually haven't said what's the problem! It compiles smoothly and start running (I guess the algorithm is correct, 'cause the program finds the correct sums up to small numbers, so it should do so for big ones too); around 250k, anyway, the sum reaches I don't know exactly what value, goes negative and start to decrement (that is, to augment...) Around 500k it reaches 0 again and starts to climb up again. Here I usually stop, 'cause I believe this shouldn't definitely be the right behavior...suggestions?

Whilst it has no functional difference, it is definitely confusing that is "isprime" returning zero rather than one when it's a prime. Please don't call a funcion isxxx and then return "false" when it IS. it should either be "isntprime" or return 0 for something that isn't a prime, and one for something that is.

To make your code run a bit faster, you may also consider starting your calculation by "knowing" that the value 2 is a prime, and testing values 3 and above. That way, you only need to test odd values, which means half the number of tests - yes, I know, checking if it's divisible by 2 is relatively easy, but it's still completely unnecessary.

Either way, You can also start your loop in isprime at three, since you have already tested for 2. And since any number above 2 that is a prime is an odd number, you don't need to check if it's divisible by even numbers - because then it would also "catch" on half that number - e.g. 52 is divisible by 26 - but you should already have tested with 13, so it's no point.

Both of these combined means your code will essentially run 4 times faster (you are testing half the numbers, and with half as many numbers).

If you know that 2 only 2 is an even prime, why not check with "if(a == 2) return 0;".

I ran one of my prime number calculators, and it came up with this sum:
37550402023 (78498 primes)

You may want to check that you get only primes with your isprime function. I haven't tested with your method - I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires LOTS of memory).

--
Mats

I suspect this is due to printf since 64 bits integer can store decimal numbers up to 18 x 10^18. The sum of the first 250 000 integers wouldn't even be close to this. So is the sum of the first 1 000 000 integers.

But maybe it's something else. Someone out here surely knows.

Oh and except for the sum variable, i would use int (or unsigned int if you wish) variable instead of fancy int64_t (which i never manipulated, in fact, i'm not sure the library you are talking about (<stdint.h>) is anything but standard). int can store number at least up to 2 billion. I'm one of those guys who, when i have to manipulate integer, will use int before everything else except if i really can't use them. Like in the case of your sum variable...

And using int may speed up the whole thing a little bit if you are on a 32 bit processor. But if you do want to speed up the process, don't call printf each time you meet a prime number.

Also, you might want to switch this

Code:

---

for(i=2; i<a/2 ; i++)

---

for this

Code:

---

for(i=2; i < sqrt(a); i++)

---

or something like

Code:

---

maxUsefulTestValue = (int) sqrt(a);
for(i=2; i < maxUsefulTestValue; i++)

---

but your compiler may have done this optimisation anyway...


In the last case, you could use some sort of BigNum librairy. But like i said, i'm quite sure this has something to do with printf, so it would be rather useless...

Quote:

---

int can store number at least up to 2 billion

---

You cant just say two billion. It would really depend on his OS and the compiler which he is using.

ssharish2005

Foxman: You make a good point. The sum of all primes up to 250000 is a bit over 2 billion, so around the point of wrapping a 32-bit number. So it seems like the the printf isn't printing a 64-bit number. Is this a MS compiler? If so, use %I64d" instead of "%lld".

--
Mats

Quote:

---

You cant just say two billion. It would really depend on his OS and the compiler which he is using.

---

Hah right, i tought the guaranteed minimal magnitude of int was 2^32 but i just checked and saw in was in fact 2^16 (in the case my documentation is up to date). But yeah, i was wrong, this isn't the guaranteed minimal magnitude for int.

Anyway.

Quote:

---

Originally Posted by foxman

Hah right, i tought the guaranteed minimal magnitude of int was 2^32 but i just checked and saw in was in fact 2^16 (in the case my documentation is up to date). But yeah, i was wrong, this isn't the guaranteed minimal magnitude for int.

Anyway.

---

I don't think there's ANY minimum guarantee for an int - only that (when it comes to size) char <= int <= long <= long long - but in theory all of them could be 8 bits on some unusually old hardware. 16-bit integers are definitely not unusual in the embedded arena where 16-bit processors are quite commonly used.

--
Mats

matsp: Well i don't know, guess we would have to check the document about C official standard.

I took my information there at cplusplus.com. They could be wrong, but i guess you know this site and agree this is a lovely C documention website. :)

But i agree on this "char <= int <= long <= long long".

[edit] I just did some research and found that in the current C standard (C99) document, at page no. 22 (page no. 34 of pdf pages), it states that int should effectively be at least 16 bits wide. But i agree that doesn't mean every compiler respect the C99 standard.

Oh, and i also found that <stdint.h> was indeed a standard library since C99. My bad. I'm not really into that C99 standard but more about the ANSI one... hehe... [/edit]

Quote:

---

Originally Posted by matsp

Whilst it has no functional difference, it is definitely confusing that is "isprime" returning zero rather than one when it's a prime. Please don't call a funcion isxxx and then return "false" when it IS. it should either be "isntprime" or return 0 for something that isn't a prime, and one for something that is.

---

i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?

Quote:

---

Originally Posted by matsp

To make your code run a bit faster, you may also consider starting your calculation by "knowing" that the value 2 is a prime, and testing values 3 and above. That way, you only need to test odd values, which means half the number of tests - yes, I know, checking if it's divisible by 2 is relatively easy, but it's still completely unnecessary.

Either way, You can also start your loop in isprime at three, since you have already tested for 2. And since any number above 2 that is a prime is an odd number, you don't need to check if it's divisible by even numbers - because then it would also "catch" on half that number - e.g. 52 is divisible by 26 - but you should already have tested with 13, so it's no point.

Both of these combined means your code will essentially run 4 times faster (you are testing half the numbers, and with half as many numbers).

If you know that 2 only 2 is an even prime, why not check with "if(a == 2) return 0;".

I ran one of my prime number calculators, and it came up with this sum:
37550402023 (78498 primes)

You may want to check that you get only primes with your isprime function. I haven't tested with your method - I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires LOTS of memory).

--
Mats

---

yeah, I was skipping even numbers in the function, now I implemented a condition in the main for loop, so to pass to the function only odd numbers!
According to this txt, my prime numbers (up to 997) are correct, so I believe are correct even after 997!

Quote:

---

Originally Posted by foxman

I suspect this is due to printf since 64 bits integer can store decimal numbers up to 18 x 10^18. The sum of the first 250 000 integers wouldn't even be close to this. So is the sum of the first 1 000 000 integers.

But maybe it's something else. Someone out here surely knows.

Oh and except for the sum variable, i would use int (or unsigned int if you wish) variable instead of fancy int64_t (which i never manipulated, in fact, i'm not sure the library you are talking about (<stdint.h>) is anything but standard). int can store number at least up to 2 billion. I'm one of those guys who, when i have to manipulate integer, will use int before everything else except if i really can't use them. Like in the case of your sum variable...

And using int may speed up the whole thing a little bit if you are on a 32 bit processor. But if you do want to speed up the process, don't call printf each time you meet a prime number.

---

Those types where inherited from previous versions of the code, I left them there without reason...now I changed them back to int, leaving only sum declared as an uintmax_t...the printfs are there for visual debugging, just to check everything is running correctly!

Quote:

---

Originally Posted by foxman

But like i said, i'm quite sure this has something to do with printf, so it would be rather useless...

---

You think so? So maybe is not my fault after all :D?!
perhaps I could try to write it in a file? Would it change something?

Quote:

---

Originally Posted by matsp

Foxman: You make a good point. The sum of all primes up to 250000 is a bit over 2 billion, so around the point of wrapping a 32-bit number. So it seems like the the printf isn't printing a 64-bit number. Is this a MS compiler? If so, use %I64d" instead of "%lld".

--
Mats

---

I'm using Eclipse's CDT...

You know what, guys? I think I64d made the trick. I changed the printf in the loop and left unchanged the one at the end of the program. I looped up to MAX/2 (just to try it out) and the first one printed "9914236195", while the last one printed "1324301603". Now I've got the program running, doing the full loop...let's see if this works!

Quote:

---

Originally Posted by Doriän

i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?

---

Not strictly, and most importantly, functions like "isdigit" or "isalpha" returns a "true/false" result, where true is considered any non-zero value, and false is zero. Your function uses this naming convention, but operates in the opposite way.

There are lots of functions where returning non-zero is an indication of success, fopen(), fread/fwrite are but a few examples where a non-zero result (or non-NULL - but as NULL and zero have the same value in most instances, I classify this as the same).

If you actually want to indicate SUCCESS/FAILURE, then you should return SUCCESS and compare with SUCCESS, not return 0 and compare with 0 - the fact that SUCCESS happens to be zero (in some systems) is besides the point.

But I still think functions that have similar names should operate in similar ways - so something called "isxxx" should return non-zero (e.g. 1) for "is" and 0 for "isn't".

Quote:

---

yeah, I was skipping even numbers in the function, now I implemented a condition in the main for loop, so to pass to the function only odd numbers!
According to this txt, my prime numbers (up to 997) are correct, so I believe are correct even after 997!

---

Sounds right then - I wasn't saying it was wrong, just that you should check it - obviously, if you are adding more numbers than you should, the number would grow larger than it should too!

Quote:

---

You think so? So maybe is not my fault after all :D?!
perhaps I could try to write it in a file? Would it change something?

---

Writing to a file using fprintf() wouldn't change anything. I don't know much abotu Eclipse CDT, so I don't know if it's printf supports 64-bit prints.

Perhaps you can use a manual conversion, like this:

Code:

---

char *lltostr(uintmax_t n, char *str, int maxlen) {
    char *s = str[maxlen-1];
    *s-- = 0;  /* Start by marking the end */
    do {
        *s--- = (char)((n % 10) + '0');
        n /= 10;
    } while(n);
    return s;
}

...
  char ss[25];
  printf("Sum = %s\n", lltostr(sum, ss, 25))
...

---

--
Mats

9914236195 is what I get for 0.5 million primes, so it looks like you've cracked it.

--
Mats

Quote:

---

Originally Posted by matsp

Not strictly, and most importantly, functions like "isdigit" or "isalpha" returns a "true/false" result, where true is considered any non-zero value, and false is zero. Your function uses this naming convention, but operates in the opposite way.

There are lots of functions where returning non-zero is an indication of success, fopen(), fread/fwrite are but a few examples where a non-zero result (or non-NULL - but as NULL and zero have the same value in most instances, I classify this as the same).

If you actually want to indicate SUCCESS/FAILURE, then you should return SUCCESS and compare with SUCCESS, not return 0 and compare with 0 - the fact that SUCCESS happens to be zero (in some systems) is besides the point.

But I still think functions that have similar names should operate in similar ways - so something called "isxxx" should return non-zero (e.g. 1) for "is" and 0 for "isn't".

---

Oh, all right, I got your point now. Is more a "standard" issue, then, am I right? Perhaps I could use EXIT_SUCCESS and EXIT_FAILURE, as declared in stdlib.h? (meh, I believe they're declared respectively as 0 and 1, so it wouldn't change really much, would it?)

Quote:

---

Originally Posted by matsp

Sounds right then - I wasn't saying it was wrong, just that you should check it - obviously, if you are adding more numbers than you should, the number would grow larger than it should too!

---

yeah, that would cause some trouble!

Quote:

---

Originally Posted by matsp

Writing to a file using fprintf() wouldn't change anything. I don't know much abotu Eclipse CDT, so I don't know if it's printf supports 64-bit prints.

Perhaps you can use a manual conversion, like this:

Code:

---

char *lltostr(uintmax_t n, char *str, int maxlen) {
    char *s = str[maxlen-1];
    *s-- = 0;  /* Start by marking the end */
    do {
        *s--- = (char)((n % 10) + '0');
        n /= 10;
    } while(n);
    return s;
}

...
  char ss[25];
  printf("Sum = %s\n", lltostr(sum, ss, 25))
...

---

---

I guess I'm lucky the CDT likes I64d, 'cause I really can't understand what this code does :D! What should I convert with it?

SUCCESS! Thanks guys, problem solved!

here's the final code, perhaps I could still learn something from errors I overlooked...

Code:

---

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

 Find the sum of all the primes below one million.*/

#include<stdio.h>
#include<stdint.h>
#include<math.h>

#define MAX 1000000

int isPrime(int a);

int main(int argc[], char *argv[]) {
    int i;
    uintmax_t sum=2;

    for (i=3; i<MAX; i++) {
        if(i%2!=0){
            if (isPrime(i)==0) {
                sum += i;
                printf("%I64d\t", sum);
                printf("%d\n", i);
            }
        }
    }
   
    printf("\n%I64d\n", sum);
    printf("Press a key to continue...\n");
    getch();   

    return (0);
}

int isPrime(int a) {
    int i;
       
    for(i=3; i<a/2 ; i++) {
        if(a%i==0) {
            return(1);
        }
    }

    return (0);
}

---

(still haven't changed return values of the function, sorry mats :))

Quote:

---

Originally Posted by Doriän

i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?

---

It often is, but you are not indicating "success" here. You are indicating whether the number is prime or not. Either way, the function obviously "succeeds" in performing its task.

Also, when a function returns 0 as a success status, typically error conditions are represented by NEGATIVE return values, not positive ones.

None of it matters functionally -- but a function named "is_xxx" is a predicate. Inverting the return values makes absolutely no sense, because it leads to code like this:

Code:

---

if(!is_prime(x))
{
    /* That line of code reads "If not is prime..." and yet it MEANS "if prime." BAD. */
}

---

Quote:

---

Originally Posted by foxman

Also, you might want to switch this

Code:

---

for(i=2; i<a/2 ; i++)

---

for this

Code:

---

for(i=2; i < sqrt(a); i++)

---

or something like

Code:

---

maxUsefulTestValue = (int) sqrt(a);
for(i=2; i < maxUsefulTestValue; i++)

---

but your compiler may have done this optimisation anyway...

---

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Having said this, it's definitely worthwhile, since for a near 1000000 you only have to go up to 1000, instead of 500000, for roughly a factor of 500 speedup for large a.

> I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires
> LOTS of memory).

Due to the improved asymptotic time over doing a primality test for each number separately, for calculating the sum of the first N primes, where N is sufficiently large, the sieve method should be faster even if it starts swapping and incurs a huge constant factor slowdown (I don't know how large N has to be to make up for the swap penalty). And in going up to a million, it only needs about a megabyte, at one byte per number (one can of course optimize by using one bit per number).

Quote:

---

Originally Posted by robatino

You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

---

Just add 1 after taking the square root. The imprecision will never be more than 1 unit, or even close to it. And the cost of checking one extra value gets less and less important the larger the number gets.

Quote:

---

Originally Posted by robatino

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Having said this, it's definitely worthwhile, since for a near 1000000 you only have to go up to 1000, instead of 500000, for roughly a factor of 500 speedup for large a.

---

Quote:

---

Originally Posted by brewbuck

Just add 1 after taking the square root. The imprecision will never be more than 1 unit, or even close to it. And the cost of checking one extra value gets less and less important the larger the number gets.

---

Done. It is indeed several times faster (I had already tried this method some time ago, in another exercise with prime numbers, but that time it didn't work - looks like I'll have to check that one too!)

I changed the return values too - switched 0s with 1s, so that now 1=success, or better, isPrime, and 0 = !isPrime.


edit: A question related to this issue of return values. In my main, I call the function in this way:

Code:

---

for (i=3; i<MAX; i++) {
                if(i&#37;2!=0){
                        if (isPrime(i)==1) {
                                sum += i;
                                printf("%I64d\t", sum);
                                printf("%d\n", i);
                        }
                }

---

If I were to call the function in this other way,

Code:

---

for (i=3; i<MAX; i++) {
                if(i%2!=0){
                        if (isPrime(i)) {  // <-- Here's the change
                                sum += i;
                                printf("%I64d\t", sum);
                                printf("%d\n", i);
                        }
                }

---

would it consider i prime if the function were to return 1 or if the function were to return 0?


edit2: Disregard that, I tried and it works fine indeed. But how's that? I mean, does the main consider "successful" the call (thus isPrime) if the function returns the last value (

Code:

---

int isPrime(int a) {
        int i;
               
        for(i=3; i<sqrt(a)+1 ; i++) {
                if(a%i==0) {
                        return(0);
                }
        }

        return (1);
}

---

, so 1 here), and unsuccessful (thus !isPrime) if it return a value which isn't the last? How does it tell the difference?

> would it consider i prime if the function were to return 1 or if the function were to return 0?
When a numeric value is used in a test (such as if, for, while), anything nonzero is true, and zero is false. Conversely, the numeric value of a true statement is 1, and of a false statement is 0 (so "i = (3 > 0);" sets i to 1, and "i = (3 == 5);" sets i to 0).

I didn't know this. Thanks!

Quote:

---

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

---

Yeah sorry, i didn't pay attention to that important point (adding one to the sqrt if you stay with the condition < and not <=). I should have, but since my post was more towards the use of printf and the differents types of integer, i went too fast on this particular part. :)

Quote:

---

Originally Posted by robatino

> I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires
> LOTS of memory).

Due to the improved asymptotic time over doing a primality test for each number separately, for calculating the sum of the first N primes, where N is sufficiently large, the sieve method should be faster even if it starts swapping and incurs a huge constant factor slowdown (I don't know how large N has to be to make up for the swap penalty). And in going up to a million, it only needs about a megabyte, at one byte per number (one can of course optimize by using one bit per number).

---

Yes, the problem for me is that I run out of possible swap-space long before I get to that point, since the OS I use (currently) is only 32-bit, and swap-space thus is limited to 3GB, which when used in "bitsieve" (which uses 1 bit per number, rather than a byte), it gives about 24 billion sieve-range - I haven't tried that... I have 2GB of RAM in the machine, so it's not going to be THAT bad, but it's MUCH worse than when it fits in memory completely. The worst part is actually for the small primes, because it's touching every few bytes, which means there's no gaps. Once you get somewhere large, it's not too bad, because the memory management only need to swap in/out the pages that are needed, which isn't all (but there's still some churn, because the next number is obviously not going to be touch the same multiples of 4KB).

--
Mats