Primes

From Algorithmist

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.

[edit] Algorithms

[edit] Naive

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

[edit] Prime Sieves

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

Prime Sieve of Atkin is more efficient.