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

Thread: prime chekcer doesnt work

  1. #1
    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. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,098

    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. #3
    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. #4
    Join Date
    Aug 2009
    Posts
    439

    Re: prime chekcer doesnt work

    Is this a typo?

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

  5. #5
    Join Date
    Mar 2006
    Posts
    139

    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. #6
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,891

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center