Sieve of Eratosthenes
If someone wants to check for a certain number n to be prime, they do as follows:
- Write numbers from 2 to that number onto a piece of paper.
Do the following:
- Get the next number that is not crossed out.
- Cross out all multiples of that number on your sheet.
Repeat this for all numbers until you reach the square root of n.
If n has been crossed out it is not prime.