Find a prime number?

Question

To find whether N is a prime number we only need to look for all numbers less or equal to sqrt(N). Why is that? I am writing a C code so trying to understand a reason behind it.

Answer 1

N is prime if it is a positive integer which is divisible by exactly two positive integers, 1 and N. Since a number's divisors cannot be larger than that number, this gives rise to a simple primality test:

• If an integer N, greater than 1, is not divisible by any integer in the range [2, N-1], then N is prime. Otherwise, N is not prime.

However, it would be nice to modify this test to make it faster. So let us investigate.

Note that the divisors of N occur in pairs. If N is divisible by a number M, then it is also divisible by N/M. For instance, 12 is divisble by 6, and so also by 2. Furthermore, if M >= sqrt(N), then N/M <= sqrt(N).

This means that if no numbers less than or equal to sqrt(N) divide N, no numbers greater than sqrt(N) divide N either (excepting 1 and N themselves), otherwise a contradiction would arise.

So we have a better test:

• If an integer N, greater than 1, is not divisible by any integer in the range [2, sqrt(N)], then N is prime. Otherwise, N is not prime.

if you consider the reasoning above, you should see that a number which passes this test also passes the first test, and a number which fails this test also fails the first test. The tests are therefore equivalent.

Answer 2

A composite number (one that is not prime, or 1) has at least 1 pair of factors, and it is guaranteed that one of the numbers from each pair is less than or equal to the square root of the number (which is what you are asking about).

If you square the square root of the number, you get the number itself (sqrt(n) * sqrt(n) = n), so if you made one of the numbers bigger (than sqrt(n)) you would have to make the other one smaller. If you then only check the numbers 2 through sqrt(n) you will have checked all of the possible factors, since each of those factors will be paired with a number that is greater than sqrt(n) (except of course if the number is in fact a square of some other number, like 4, 9, 16, etc...but that doesn't matter since you know they aren't prime; they are easily factored by sqrt(n) itself).

Answer 3

Because in the worst case, number n can be expresed as a².

If the number can be expressed diferently, that men that one of divisors will be less than a = sqrt(n), but the other can be greater.

Answer 4

The reason is simple, any number bigger than the sqrt, will cause the other multiplier, to be smaller than the sqrt. In such case, you should have already check it.

Answer 5

Let n=a×b be composite.

Assume a>sqrt(n) and b>sqrt(n).

a×b > sqrt(n)×sqrt(n)

a×b > n

But we know a×b=n, therefore a<sqrt(n) or b<sqrt(n).

Since you only need to know a or b to show n is composite, you only need to check the numbers up to sqrt(n) to find such a number.