Primality Test - Naive Methods

Naive Methods

The simplest primality test is as follows: Given an input number n, check whether any integer m from 2 to n/2 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

However, rather than testing all m up to n/2, it is only necessary to test m up to : if n is composite then it can be factored into two values, at least one of which must be less than or equal to .

The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does. It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.

Generalising further, it can be seen that all primes are of the form c#k + i for i < c# where i represents the numbers that are coprime to c# and where c and k are integers. For example, let c = 6. Then c# = 2 3 5 = 30. All integers are of the form 30k + i for i = 0, 1, 2,...,29 and k an integer. However, 2 divides 0, 2, 4,...,28 and 3 divides 0, 3, 6,...,27 and 5 divides 0, 5, 10,...,25. So all prime numbers are of the form 30k + i for i = 1, 7, 11, 13, 17, 19, 23, 29 (i.e. for i < 30 such that gcd(i,30) = 1). Note that if i and 30 are not coprime, then 30k + i is divisible by a prime divisor of 30, namely 2, 3 or 5, and is therefore not prime.

As c → ∞, the number of values that c#k + i can take over a certain range decreases, and so the time to test n decreases. For this method, it is also necessary to check for divisibility by all primes that are less than c. Observations analogous to the preceding can be applied recursively, giving the Sieve of Eratosthenes.

A good way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, say all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes). Then, before testing n for primality with a serious method, n can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.

A simple, but very inefficient primality test uses Wilson's theorem, which states that p is prime if and only if:

Although this method requires about p modular multiplications, rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.