Sieve of Eratosthenes

Sieve_of_Eratosthenes_animation

everybody has already read about the the ancient Greek mathematician Eratosthenes (250 BCE).  A basic algorithm could be found at http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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.
Advertisements