prime chekcer doesnt work
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: prime chekcer doesnt work

1. Member
Join Date
Jun 2012
Posts
58

## 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?

2. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

## 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?

3. Member
Join Date
Jun 2012
Posts
58

## 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. :/

4. Member
Join Date
Aug 2009
Posts
440

## Re: prime chekcer doesnt work

Is this a typo?

Code:
`	for(c=2; c<max; i++)`
Otherwise, it looks like it should work.

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

6. Elite Member Power Poster
Join Date
Apr 2000
Location
Belgium (Europe)
Posts
4,626

## 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
•