Prime Number Checker (next & previous prime)

Understanding the prime number checker — concept and principle

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. This checker tells you whether a number is prime, shows its prime factorization if it is not, and finds the nearest primes above and below it. It is useful for homework, puzzles, programming exercises, and quick checks before using a number as a hash size or in a math proof.

How it is calculated

1. Numbers below 2 are not prime; 2 and 3 are prime.
2. If n is divisible by 2 or 3, it is composite (unless it is 2 or 3).
3. Otherwise test divisors of the form 6k − 1 and 6k + 1 (5, 7, 11, 13, 17, 19 …) while the divisor is at most √n. If none divides n, n is prime.
4. Next prime: test n + 1, n + 2, … until a prime is found. Previous prime: test n − 1, n − 2, … down to 2.

The principle

If n had a factor larger than √n, its partner factor would be smaller than √n, so checking up to √n is enough. Every integer can be written as 6k, 6k ± 1, 6k + 2, 6k + 3 or 6k + 4; the forms 6k, 6k + 2 and 6k + 4 are even and 6k + 3 is a multiple of 3. So after removing 2 and 3, every remaining prime is 6k ± 1, which skips two-thirds of the candidates. Euclid proved more than two thousand years ago that there are infinitely many primes, so a next prime always exists.

Worked example

1. Input: 97. √97 ≈ 9.85, so only divisors up to 9 matter.
2. 97 is odd and its digit sum 16 is not a multiple of 3.
3. 6k ± 1 candidates up to 9: 5 and 7. 97 ÷ 5 = 19.4 and 97 ÷ 7 ≈ 13.86, neither exact.
4. Result: yes, 97 is prime.
5. Next prime: 98, 99 and 100 are composite; 101 is prime, so 101.
6. Previous prime: 96 down to 90 are all composite; 89 is prime, so 89.

How to read the result

"no" is followed by the factorization, which shows the smallest factor first. The distance between the previous and next prime is a prime gap; here 89 to 97 is a gap of 8, unusually large for numbers this size. On average, primes near n are about ln n apart, so they thin out slowly as numbers grow.

Common mistakes

• Calling 1 a prime. By modern convention it is not, which keeps factorizations unique.
• Assuming every odd number is prime: 91 = 7 × 13 is a common trap.
• Testing only up to n/2 instead of √n, which is correct but needlessly slow.

Frequently asked questions

Is 2 the only even prime?

Yes. Every other even number is divisible by 2 and so has at least three divisors.

How many primes are there below 100?

There are 25, from 2 to 97. 97 is the largest two-digit prime.

How do computers test huge numbers for primality?

They use probabilistic tests such as Miller–Rabin or proven methods such as the AKS or elliptic-curve tests, which are far faster than trial division.

Sources: Euclid, Elements, Book IX, Proposition 20 (infinitude of primes) · G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chapters 1–2 · M. Agrawal, N. Kayal and N. Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004)