Prime Number Checker

Is 91 prime? It looks like it might be, but it's 7 times 13. This tool tells you whether a number is prime and, if not, breaks it into prime factors. For primes it shows the nearest primes either side. It can also list every prime up to a limit. Numbers up to one trillion are supported.

How to use it

1. Choose whether to check one number or list primes.
2. Enter the number.
3. Read the verdict, the factors or the list.
4. Copy it if you need it.

When it helps

• Homework and puzzles.
• Factorising a number into primes.
• Finding primes for a small programme or exercise.
• Exploring number patterns.

Good to know

• A prime has exactly two divisors, 1 and itself, which is why 1 itself isn't prime.
• The list mode goes up to 100,000.
• 2 is the only even prime.

How primality is tested

The tool checks whether the number is divisible by 2 or 3, then tests divisors of the form 6k plus or minus 1 up to the square root of the number. If none divides it, it's prime. That's fast enough for numbers up to a trillion, since the square root is at most a million.

For huge numbers, such as those used in encryption, different methods are needed.

Worked example: 91 and 97

91 looks prime, but 7 times 13 is 91. The tool tests 7 and finds it divides evenly, so 91 is composite. 97 has no divisors up to 9, which is its square root rounded down, so it's prime. The previous prime is 89 and the next is 101.

Try 561, which fools some simple tests but is 3 times 11 times 17.

Why primes matter

Primes are the building blocks of whole numbers, and they underpin modern encryption: RSA relies on how hard it is to factor the product of two huge primes. They also appear in hashing, random number generators and error-correcting codes.

There are infinitely many primes, a fact Euclid proved over two thousand years ago, and the largest known has tens of millions of digits.

Primes up to a limit

The list mode uses the sieve of Eratosthenes: start with all numbers, cross out multiples of 2, then 3, then 5 and so on. What's left are the primes. There are 25 primes below 100, 168 below 1,000 and 9,592 below 100,000.

Notice that primes thin out slowly: about one in every ln(n) numbers near n is prime.

Famous primes

Twin primes are pairs that differ by two, such as 11 and 13, or 17 and 19. Mersenne primes have the form two to the power n minus one, like 31 and 127, and the largest known primes are of this kind. Whether there are infinitely many twin primes is still an open question.

Goldbach's conjecture, that every even number above two is the sum of two primes, has been checked to enormous sizes but remains unproved.

Questions