Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

When I was in college and as a programming language learner I wrote program for finding out prime numbers but then I never mind the program performance in terms of speed. Now after long time just started solving the problems from projecteuler.net.

Now I wonder is there any best and most used algorithm for finding the primality of a given positive number which produces the result fast?

Thanks

share|improve this question

closed as not a real question by Robert Harvey, Yannis Rizos, blueberryfields, StuperUser, ChrisF Nov 24 '11 at 23:47

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
    
1  
3  
1  
Yes, the Wikipedia link specifically states "When the numbers are very large, no efficient integer factorization algorithm is known." –  Robert Harvey Nov 21 '11 at 17:03
show 4 more comments

3 Answers 3

up vote 5 down vote accepted

For prime testing of very large numbers, there are probabilistic methods:

http://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests

Most popular primality tests are probabilistic tests. These tests use, apart from the tested number n, some other numbers a which are chosen at random from some sample space; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of a...

share|improve this answer
    
The Miller-Rabin test is simple, easy to implement, and does what you want. The alternatives like the sieve won't help you with determining primality of a 9 or 15 digit number as you will often want on Project Euler. –  Brian Nov 22 '11 at 6:06
add comment

The fastest way is going to be a lookup table:

This page indexes many of the lists of primes stored at this site. The main list we keep is the list of the 5000 largest known primes and selected smaller primes. We also have list of the first primes, but it is not practical to keep too long of such list...

share|improve this answer
    
+1. I've solved more than 200 of the Project Euler questions and for all the ones where I needed to test primes I got by fine with a lookup table which I filled to a safe upper bound using a naïve sieve. –  Peter Taylor Nov 21 '11 at 22:23
    
looking up can be slow if the table is big enough to need to be paged out ;-) –  fortran Nov 23 '11 at 16:23
add comment

One very fast method of Rejecting a trial prime is to use that fact that all primes are of the form 6k +/- 1, where k is a positive integer. (2 and 3 excepted).

This means you can reject a number with only two tests (plus the trivial).

public static boolean checkPrime(long p)
{
   if (p==2 || p==3) return true;
   if ( (p+1) % 6 == 0 || (p-1) % 6 == 0 ) 
   {
      // p might be prime, worth checking
      return checkProbablePrime(p);
   }
   else
   {
     // p is not prime.
     return false;  
   }
} 

Whether or not this is a good technique depends on the distribution of inputs. If you expect a high percentage of composite numbers, then this is a quick way of eliminating them from contention. It would be nice to eliminate the trivial branch at the top (==2, ==3) but that depends on the context of the inputs. If your goal is to FIND primes, then you should skip this.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.