The most efficient way to find all of the small primes (say all those less than 10,000,000) is by using a sieve such as the Sieve of Eratosthenes.

**Algorithm:**

Input: an integer *n* > 1

Let *A* be an array of Boolean values, indexed by integers 2 to *n*,

initially all set to true.

for *i* = 2, 3, 4, …, not exceeding *√n*:

if *A*[*i*] is true:

for *j* = *i^2*, *i^2 + i*, *i^2 + 2i*, …, not exceeding *n* :

* A*[*j*] := false

**Explanation: **

Let’s find all primes from less than 25, we have

The first number 2 is prime, so keep it (color it green) and cross out its multiples (color them red), so the red numbers are not prime.

The first number left (still black) is 3, so it is the first odd prime. Keep it and cross out all of its multiples. We know that all multiples less than 9 (i.e. 6) will already have been crossed out, so we can start crossing out at [math]3^2 = 9[/math].

Now the first number left (still black) is 5, the second odd prime. So keep it also and cross out all of its multiples (all multiples less than [math]5^2 = 25[/math] have already been crossed out, and in fact 25 is the only multiple not yet crossed out).

The next number left, 7, is larger than the square root of 25, so there are no multiples of 7 to cross off that haven’t already been crossed off (14 by 2, and 21 by 3), and therefore the sieve is complete. Therefore all of the numbers left are primes: {2, 3, 5, 7, 11, 13, 17, 19, 23}.

And we are done!

BTW the best way to understand this is by this gif. File:Sieve of Eratosthenes animation.gif

I posted it here.

Reblogged this on Jithu R Jacob and commented:

A good solution to find prime numbers I think

LikeLike