Why is the square root the key to the Sieve of Eratosthenes and finding prime numbers?

Answer 1

Let p be the number we are testing for primality.

The reason we don't have to check beyong sqrt(p) is if any number n larger than sqrt(p) divides p, then p/n, which is greater than n, also divides p.

Consider the following example with 101.

We check to see that 2, 3, 5, and 7 do not divide 101.

11*11 = 121 implies 11*X = 101 only if X is smaller than 11. But we already checked the numbers smaller than 11.

Answer 2

The Sieve of Eratosthenes is a method used to find all prime numbers up to a given limit. The square root is utilized in this sieve because if a number has a factor larger than its square root, then it must also have a corresponding factor smaller than its square root. Therefore, by only checking numbers up to the square root of the given limit, we can effectively identify all the prime numbers.