Primes

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

Primes are numbers that are building blocks of integers. These integers can only be divided even by 1 and itself. Every other positive integer can be represented by product of these numbers. There are no formulas for the set of primes.

Algorithms[edit]

Naive[edit]

The simpliest idea to test primality would be just to test if it is divisible by any smaller number (other than 1). If it cannot, then it is a prime.

Thus, the naive way to find all primes (up to N) would be something like this:

func gen_primes( var N )
   for i from 2 to N
      for j from 2 to i - 1
         if j divides i
            i is not a prime

Under the naive algorithm, there are a few optimizations available:

  • You only need to divide by numbers upto the square root of the number being tested.
  • If you are constructing a list of primes, then you only need to divide by the primes already obtained.
  • If you do not have a list of primes, you can first check for divisibility by

Prime Sieves[edit]

Prime Sieve of Eratosthenes is perhaps the earliest and the most well-known of the sieves.

Prime Sieve of Atkin is more efficient.

Probable primes[edit]

The Fermat test uses the formula a^{{n-1}}\,{\bmod  \,}n=1, where n is the number being tested. If the formula holds when a is a random integer between 2 and n-1, the number is probably prime. This test produces false positives, known as Carmichael Numbers.

Storing[edit]

If you want to have a prime number lookup table, you can do a simple test for divisibility by 2, 3, and 5. In all other numbers, you can divide the number being tested by 30 and keep track of the remainder. If the remainder is not one of 1, 7, 11, 13, 17, 19, 23 or 29, it is composite. If it is, these eight numbers can map directly to 8-bits of a byte for a lookup table.