3

Alright, so maybe I shouldn't have shrunk this question sooo much... I have seen the post on the most efficient way to find the first 10000 primes. I'm looking for all possible ways. The goal is to have a one stop shop for primality tests. Any and all tests people know for finding prime numbers are welcome.

And so:

  • What are all the different ways of finding primes?
Community
  • 1
  • 1
akdom
  • 32,264
  • 27
  • 73
  • 79
  • Note that you can count the number of primes below n without computing all of them: https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29 – Jeffrey Bosboom Jul 13 '15 at 01:20

8 Answers8

3

Some prime tests only work with certain numbers, for instance, the Lucas–Lehmer test only works for Mersenne numbers.

Most prime tests used for big numbers can only tell you that a certain number is "probably prime" (or, if the number fails the test, it is definitely not prime). Usually you can continue the algorithm until you have a very high probability of a number being prime.

Have a look at this page and especially its "See Also" section.

The Miller-Rabin test is, I think, one of the best tests. In its standard form it gives you probable primes - though it has been shown that if you apply the test to a number beneath 3.4*10^14, and it passes the test for each parameter 2, 3, 5, 7, 11, 13 and 17, it is definitely prime.

The AKS test was the first deterministic, proven, general, polynomial-time test. However, to the best of my knowledge, its best implementation turns out to be slower than other tests unless the input is ridiculously large.

Artelius
  • 48,337
  • 13
  • 89
  • 105
2

The Sieve of Eratosthenes is a decent algorithm:

  1. Take the list of positive integers 2 to any given Ceiling.
  2. Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.
  3. Repeat step two until you reach the given Ceiling.
  4. Your list is now composed purely of primes.

There is a functional limit to this algorithm in that it exchanges speed for memory. When generating very large lists of primes the memory capacity needed skyrockets.

akdom
  • 32,264
  • 27
  • 73
  • 79
  • the crucial detail is missing here: how do you find, and how do you "remove" the multiples. If you find them in a proper way, i.e. counting up from a prime in steps of that prime, **you can't remove them at all**, because then you **can't count**. The point to SoE is *marking* the multiples, using their *values* as *addresses*, without any comparison of values (thus avoiding extra `log n` factor in complexity). This is exactly like what makes integer sorts faster than comparison sorts. You forgo that advantage if you're actually *removing* them. – Will Ness Sep 20 '12 at 03:41
2

For a given integer, the fastest primality check I know is:

  1. Take a list of 2 to the square root of the integer.
  2. Loop through the list, taking the remainder of the integer / current number
    1. If the remainder is zero for any number in the list, then the integer is not prime.
    2. If the remainder was non-zero for all numbers in the list, then the integer is prime.

It uses significantly less memory than The Sieve of Eratosthenes and is generally faster for individual numbers.

akdom
  • 32,264
  • 27
  • 73
  • 79
2

@akdom's question to me:

Looping would work fine on my previous suggestion, and you don't need to do any calculations to determine if a number is even; in your loop, simply skip every even number, as shown below:

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}
goric
  • 11,491
  • 7
  • 53
  • 69
2

A Rutgers grad student recently found a recurrence relation that generates primes. The difference of its successive numbers will generate either primes or 1's.

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)).

It makes a lot of crap that needs to be filtered out. Benoit Cloitre also has this recurrence that does a similar task:

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

then the ratio of successive numbers, minus one [b(n)/b(n-1)-1] is prime. A full account of all this can be read at Recursivity.

For the sieve, you can do better by using a wheel instead of adding one each time, check out the Improved Incremental Prime Number Sieves. Here is an example of a wheel. Let's look at the numbers, 2 and 5 to ignore. Their wheel is, [2,4,2,2].

nlucaroni
  • 47,556
  • 6
  • 64
  • 86
0

In your algorithm using the list from 2 to the root of the integer, you can improve performance by only testing odd numbers after 2. That is, your list only needs to contain 2 and all odd numbers from 3 to the square root of the integer. This cuts the number of times you loop in half without introducing any more complexity.

goric
  • 11,491
  • 7
  • 53
  • 69
0

@theprise

If I were wanting to use an incrementing loop instead of an instantiated list (problems with memory for massive numbers...), what would be a good way to do that without building the list?

It doesn't seem like it would be cheaper to do a divisibility check for the given integer (X % 3) than just the check for the normal number (N % X).

akdom
  • 32,264
  • 27
  • 73
  • 79
-1

If you're wanting to find a way of generating prime numbers, this have been covered in a previous question.

Community
  • 1
  • 1
GateKiller
  • 74,180
  • 73
  • 171
  • 204