prime chekcer doesnt work

[tuli]

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.

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?

[GCDEF]

Is he saying it doesn't work, or just asking if it looks okay? Do you know of a number that doesn't work?

[tuli]

He knows it doesnt work, but he doesnt know what is wrong. No specific, unfortunately, and as i said, it looks OK to me. :/

[Alterah]

Is this a typo?

	for(c=2; c<max; i++)

Otherwise, it looks like it should work.

[GeoRanger]

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").

[OReubens]

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.