Sieve of Eratosthenes


everybody has already read about the the ancient Greek mathematician Eratosthenes (250 BCE).  A basic algorithm could be found at

but why in the optimizing algorithm, the variable i should not exceed square root of n ?

  • If n is a composite integer (not a prime one), then it has a prime divisor p not exceeding square root of n. Indeed, as above, n = ab, where 2 < a ≤ b and a is the smallest divisor of n. a is prime number because if it was a composite, it will mean that a number dividing a,  will divide as well n which is in contradiction with a is the smallest divisor,  Then n ≥ a * a and  a is prime
  • Now if you want to make a basic test if a number K is prime , you have to try to divide by all the prime number below the square root of K.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s