Sieve of Eratosthenes

Tags

algorithm

Is an algorithm for quickly finding all the prime-numbers up-to any given limit.

The sieve works by filling a pad of all the numbers up-to the limit \( n \). We then scratch off the first number as prime and then mark-off all of its multiples as non-prime (because their factors of the last marked prime number). Then we scratch off the next non-marked number as prime and repeat the process.