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
