2

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

Improve this question
9

3 Answers 3

Reset to default
5

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

Improve this answer
1
  • 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, 2011 at 6:06
2

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

Improve this answer
2
  • +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, 2011 at 22:23
  • looking up can be slow if the table is big enough to need to be paged out ;-)
    – fortran
    Nov 23, 2011 at 16:23
1

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.

Improve this answer

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