With this procedure we find primes numbers ??up to a number.


 

eratosthenes


Eratosthenes of Cirene (276-194 A.C.) was a Greek scholar who lived about two hundred years ago and invented a method to find the prime numbers less than n (while useful for any given number)

It’s just a list or tab where appear the first n numbers and crossed with the not prime numbers:

Sieve of Eratosthenes animated


PROCEDURE

1.Write all numbers are written in order up to n
2.Cross out the multiples of 2 {4,6,8,10,12,14,16….} (In the picture the 2 it’s not crossed but is included like a prime)
3.Search next uncrossed number (3 in this case)
4.Cross out the multiples of this number
5.While can keep crossing return to step 3

The uncrossed numbers are the prime numbers up to n. In the picture primes up to 120.

This is a simple method to obtain the first n prime numbers . Although require store the numbers, with some possible optimizations like not store multiples of 2, 3 or 5.

Share this!
Share on Facebook0Share on Tumblr0Tweet about this on TwitterShare on Reddit0Share on StumbleUpon0Share on Google+0Email this to someone