Prime numbers

A

**prime number** (or a

**prime**) is a

natural number which has exactly two

**distinct** natural number

divisors: 1 and itself.

Prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,...

The number *1* is by definition not a prime number.

A **composite number** is a whole number greater than one that has more than two factors.

Composite numbers are:

4, 6, 8, 9, 10, 12, 14, 15,...

A simple ancient algorithm for finding all prime numbers up to a specified integer, n, is the **Sieve of Eratosthenes**:

- Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
- Mark the number 1 as special (it is neither prime nor composite).
- Cross out all numbers >2 which are divisible by 2 (every second number).
- Find the smallest remaining number >2. It is 3. So cross out all numbers >3 which are divisible by 3 (every third number).
- Find the smallest remaining number >3. It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).
Continue until you have crossed out all numbers divisible by

- Put the remaining unmarked numbers in the sequence on your list of prime numbers.