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.
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%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?