A prime number is a positive whole number (natural number) which cannot be divided into smaller whole numbers. In short, it can only be divided (integer division) by itself and 1.
First prime number is 2, then 3, 5, 7, 11, 13, 17, 19,
To generate a list of prime numbers the Greek Eratoshenes used a method called now the sieve Eratosthenes.
- Write all the natural numbers up to some chosen limit (100, 259, any limit )
- Remove 1 by crossing it ( 1 is no longer considered prime).
- The first prime number is 2. Circle the number 2.
- Go through the whole list crossing out all the numbers that are multiple of 2, that is 4, 6, 8,10,12, ...
- Repeat.
- The next prime number is 3 since it was not crossed out as a multiple of 2. Circle 3.
- Go through the whole list crossing all the numbers that are multiples of 3, and which have not already been crossed out as multiples of 2 .
- Number 4 has been crossed out already.
- Next prime number is 5. Circle 5
- Go through the whole list crossing all the numbers that are multiple of 5 and which have not been crossed out already as multiples of 2, or 3
- Repeat:
- Next prime number is 7. Circle 7
- Go through the whole list again, crossing out the multiples of 7, and so on.
If you want to test the primality of a positive integer (odd number) starting by dividing it by 3 (use divisibility rules or otherwise), then divide by 5, by seven, and
all subsequent prime numbers. If it is not divisible by any prime number, keep going but do not exceed the prime number that is closest yet smaller than square root of your number.
Enjoy.
×