Prime Number Checker

What is a prime number, and when do you need to check one?

A prime number is a natural number greater than 1 whose only divisors are 1 and itself. Seven is prime because only 1 and 7 divide it evenly; eight is not, because 2 and 4 divide it as well. A number greater than 1 that is not prime is called composite. Primes come up in homework on factors and multiples, in picking table sizes or moduli when you write code, in calendar and cycle puzzles, and in programming exercises on primality testing. This tool tells you whether a single number is prime, gives the prime factorization when it is composite, and lists every prime up to 10,000.

How the test works: only divide up to the square root

If n is composite it can be written as n = a × b with 1 < a ≤ b. Since a is no larger than b, a × a ≤ n, so a ≤ √n. That means a composite number always has a divisor other than 1 somewhere at or below its square root. If none of the numbers from 2 up to √n divides n, then n must be prime. The tool trims this further: it handles 2 first, then tries only the odd divisors 3, 5, 7, and so on, because every even number has already been ruled out by the check for 2.

n is prime if no d with 2 ≤ d ≤ √n divides n

This is plain trial division. It does not use BigInt, and it does not use probabilistic tests such as Miller-Rabin. It works on ordinary JavaScript numbers, which are exact for integers up to 2^53 − 1 (about 9 quadrillion), and the tool accepts integers up to 10^15. In the worst case, a prime close to 10^15, the loop makes roughly 16 million divisions; in a quick trial on a desktop machine that took about a tenth of a second, though speed depends on your device. The list generator runs the same test on every number up to your limit. For large ranges a sieve is far faster: it crosses off multiples of each prime in turn. The tables below were produced at build time with a sieve of Eratosthenes up to 1,000,000.

The 25 primes below 100

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

There are 35 pairs of twin primes (primes that differ by 2, such as 3 and 5, 5 and 7, 11 and 13) among the primes up to 1,000. In other places the gaps between neighbouring primes grow. The table shows where a gap of a new record size first appears, for gaps of 6, 8 and 14 or more; each row gives the prime and the next prime after it.

How many primes are there? The π(x) table

The number of primes up to x is written π(x). The prime number theorem says π(x) gets closer and closer to x / ln x as x grows. The table compares the actual count with that estimate.

There are 1,229 primes up to 10,000, which is why the list feature never shows more than 1,229. Primes thin out as numbers grow, but there are infinitely many of them, as Euclid proved.

Worked examples

Example 1: 97. √97 is about 9.85, so only the divisors 3, 5, 7 and 9 need trying. None divides 97 evenly, so 97 is prime.

Example 2: 91. This one is often mistaken for a prime. It is not divisible by 3 or 5, but 91 ÷ 7 = 13, so 91 = 7 × 13. It is composite.

Example 3: factorizing 360. 2^3 × 3^2 × 5. Every composite number can be written as a product of primes in exactly one way, up to order. This is the fundamental theorem of arithmetic.

Example 4: 2^31 − 1 = 2,147,483,647. This Mersenne number is prime. To prove it you only need to try the 23,169 odd divisors from 3 up to √n ≈ 46,340. A number above two billion is settled with about twenty-three thousand divisions.

Common misunderstandings and limits

• 1 is not prime. The definition requires a number greater than 1. If 1 counted, factorizations would no longer be unique (6 = 2 × 3 = 1 × 2 × 3 = …).
• 2 is the only even prime. Every other even number is divisible by 2 and is composite.
• The last digit alone does not settle it. Numbers ending in 1, 3, 7 or 9 can still be composite (91, 119, 143).
• Not every prime is odd. The statement "primes are odd" is false because of 2.
• Very large numbers are out of scope. The checker handles integers up to 10^15 with trial division. It cannot test numbers with hundreds of digits or generate cryptographic primes.
• The list stops at 10,000. Larger limits are capped to keep the page responsive.
• Decimals and negatives are rejected. Only whole numbers of 1 or more are accepted.

What to do with the result

When a number is composite, the factorization lets you work out other things. The number of divisors is the product of each exponent plus one, so 360 = 2^3 × 3^2 × 5 has (3 + 1)(2 + 1)(1 + 1) = 24 divisors. You can also read off greatest common divisors and least common multiples from the prime exponents. In programming, primes are often chosen as hash table sizes or as moduli in simple random number generators, because remainders then repeat their pattern less often. In cryptography, schemes such as RSA rely on the fact that multiplying two large primes is easy while recovering them from the product is hard. The primes used there are hundreds of digits long, far beyond this tool, so do not use it to create keys.

Frequently Asked Questions

Related tools

• Number base converter
• Magic square generator
• Random number generator