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.
