Primality testing

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might be called compositeness tests instead of primality tests.

The simplest primality test is trial division: Given an input number n, check whether any prime integer m from 2 to √n evenly divides n (the division leaves no remainder). If n is divisible by any m then n is composite, otherwise it is prime.

For example, we can do a trial division to test the primality of 100. Let's look at all the divisors of 100:

Here we see that the largest factor is 100/2 = 50. This is true for all n: all divisors are less than or equal to n/2. If we take a closer look at the divisors, we will see that some of them are redundant. If we write the list differently:

the redundancy becomes obvious. Once we reach 10, which is √100, the divisors just flip around and repeat. Therefore, we can further eliminate testing divisors greater than √n. We can also eliminate all the even numbers greater than 2, since if an even number can divide n, so can 2.

...
Wikipedia