What is a prime number?
Prime number is a number, which have exactly two distinct natural number divisors, 1 and itself. The most naive approach to check whether a number is prime is to follow the definition. Algorithm to check number's n primality:
if number is 1, return false;
otherwise, for all integers m from 2 to n - 1, check if n is divisible by m. If it is, n is composite;
if no divisors were found, we can conclude, that n is prime.
Note. The 1 is not a prime number, because it doesn't satisfy the definition.
Improving the method
Can we make this simple approach better? Yes. First, let us notice, that we can check divisors less or equal to square root of n only. The proof follows.
Statement. If n has a divisor d (1 < d < n), than it has a divisor d0 (1 < d0 < √n).
If n is divided by square root entirely, than it is a perfect square and not prime. Otherwise, assume, that first found divisor is d1, √n < d1 < n. But n is divided entirely by d2 = n / d1, which is less than √n. Therefore, the assumption is false and if there are a divisor greater than √n, than there is a "pair" less than √n. Statement is proven.
One more improvement
We should mention one more improvement. Assume, than n is odd (2 is not a divisor). If n is not divisible by 2 without remainder, than it is not divisible entirely by any other even number. The algorithm after those two improvements changes:
if number is 1, return false;
if number is 2, return true;
if number is even, return false;
otherwise, for all odd integers m from 3 to √n, check if n is divisible by m. If it is, n is composite;
if no divisors were found, we can conclude, that n is prime.
Generalization of this idea is when algorithm checks prime divisors only.
C++ implementation
bool isPrime(int number) {
if (number == 1)
return false;
if (number == 2)
return true;
if (number % 2 == 0)
return false;
for (int d = 3; d <= (int)sqrt((double)number); d++)
if (number % d == 0)
return false;
return true;
}
