Primality Test — Definition, Formula & Examples

A primality test is a method or algorithm used to determine whether a given positive integer is a prime number. The simplest approach, called trial division, checks whether any integer from 2 up to the square root of the number divides it evenly.

A primality test is a decision procedure that, given an integer $n \geq 2$ , outputs 'prime' if $n$ has no positive divisors other than $1$ and $n$ , and 'composite' otherwise. Trial division tests all potential factors $d$ where $2 \leq d \leq \lfloor\sqrt{n}\rfloor$ ; if none divides $n$ , then $n$ is prime.

Key Formula

\text{Check all } d \text{ where } 2 \leq d \leq \lfloor\sqrt{n}\rfloor

Where:

$n$ = The positive integer being tested for primality
$d$ = A candidate divisor
$\lfloor\sqrt{n}\rfloor$ = The largest integer not exceeding the square root of n

How It Works

To test whether

n

is prime by trial division, divide

n

by every integer

d

from 2 up to

\lfloor\sqrt{n}\rfloor

. If any

d

divides

n

evenly (with remainder 0), then

n

is composite. If none of them divide

n

, then

n

is prime. You only need to check up to

\sqrt{n}

because if

n = a \times b

and both

a

and

b

are greater than

\sqrt{n}

, then

a \times b > n

, which is a contradiction. For efficiency, you can skip even candidates after checking 2.

Worked Example

Problem: Determine whether 97 is prime using trial division.

Step 1: Compute the square root of 97 and round down to find the upper bound for trial divisors.

\lfloor\sqrt{97}\rfloor = \lfloor 9.849\ldots \rfloor = 9

Step 2: Test each integer from 2 to 9 as a divisor of 97. We only need to check primes: 2, 3, 5, and 7.

97 \div 2 = 48\text{ R }1,\quad 97 \div 3 = 32\text{ R }1,\quad 97 \div 5 = 19\text{ R }2,\quad 97 \div 7 = 13\text{ R }6

Step 3: None of these divisions produced a remainder of 0, so no integer from 2 to 9 divides 97 evenly.

Answer: 97 is prime.

Why It Matters

Primality tests are foundational in cryptography — RSA encryption relies on the difficulty of factoring large numbers while making it easy to verify that each factor is prime. In math competitions and number theory courses, efficient primality testing is a core skill for solving problems about divisibility and prime decomposition.

Common Mistakes

Mistake: Checking divisors all the way up to n − 1 instead of stopping at the square root of n.

Correction: You only need to test divisors up to

\lfloor\sqrt{n}\rfloor

. If n has a factor larger than its square root, it must also have a corresponding factor smaller than its square root.