-
November 21st, 2012, 03:10 PM
#1
prime chekcer doesnt work
hi,
A student approached me and asked why his prime checker wouldnt work. I took a look and it should work, imo, for all < 64 bit inputs.
Code:
int isitprime(unsigned long long in)
{
unsigned long long c;
unsigned long long max = sqrt(in);
if(in <= 1 )
return 0;
if(in == 2)
return 1;
for(c=2; c<max; i++)
{
if(in%c == 0)
return 0;
}
return 1;
}
checked for a bunch of primes i could think of 0,1,2,3,4,5,6,7 up to 18446744073709551557, which is supposed to be one of the largest 64 bit primes. Worked.
Does anyone see a mistake here?
-
November 21st, 2012, 03:15 PM
#2
Re: prime chekcer doesnt work
Is he saying it doesn't work, or just asking if it looks okay? Do you know of a number that doesn't work?
-
November 21st, 2012, 04:07 PM
#3
Re: prime chekcer doesnt work
He knows it doesnt work, but he doesnt know what is wrong. No specific, unfortunately, and as i said, it looks OK to me. :/
-
November 21st, 2012, 04:24 PM
#4
Re: prime chekcer doesnt work
Is this a typo?
Code:
for(c=2; c<max; i++)
Otherwise, it looks like it should work.
-
November 22nd, 2012, 12:07 AM
#5
Re: prime chekcer doesnt work
Won't this misidentify the square of a prime number as a prime?
For instance, if the argument is 9, then max is 3, the loop iterates only on 2 and doesn't check 3 because of "c < max" (which should be "c <= max"). The loop terminates and 1 is returned. You might also have a problem depending on how your sqrt function rounds or truncates, since the result is an integer. You may need to change to "max = sqrt(in) + 1;", though I can't think of an example where this is a problem.
I would also be concerned about the speed. You could gain speed on the average of a large number of runs by keeping a table of the first N primes and checking if they are a factor before going into the brute-force method, and then starting c after the last prime in the table. You could also gain a little speed by starting c on an odd number and incrementing it by 2 instead of 1. If you want to get even more sophisticated, research primality tests which use "Fermat's Little Theorem" (not to be confused with "Fermat's Last Theorem").
-
November 22nd, 2012, 12:16 PM
#6
Re: prime chekcer doesnt work
also. sqrt(), taking a double and returning a double won't be fully handling all 64bit integer values since the double mantissa is only 53 bits (1 implied 1, + 52 explicit bits).
converting some 64bit ints to double will clip the value, which will result in the returned value to be too low. the +1 georanger talked about could be enough to overcome this, but you'd have to do error analysis on it to be sure.
Primality remains to be one of the "hard" problems, and a main reason why cryptography on pc's using primes is still feasible. Prooving a number IS a prime with 100% certainty is still hard.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|