The Sieve?

The sieve of Eratosthenes.
(Eratosthenes: 275 B.C.E. ~ 194 B.C.E.)


n: Target integer
i) let integer L be the square root of n /* square root is not essential L=n/2 or even L=n will do*/

ii) let {a(2),a(3), ..,a(n)} be an array with initial value 1 for every component
a(2)=1,
a(3)=1,
..
a(k)=1,
..
a(n)=1.

iii) for every k=2,..,L,

if a(k)=1,
for every j with k<j<=L, if k devides j then put a(j)=0;
else if a(k)=0, continue next step.
if k=L, stop the iteration
if k<L, k=k+1 (continue).

iv) the outcome array {a(2), a(3), .., a(n)} gives all the primes not greater than n, i.e.,

if a(i)=0 then i is a composite number,
if a(i)=1 then i is a prime.

satt:

Thanks.

For the uninitiated, this is a common way to test how fast a computer can run.