Prime number calculator
Enter a number, find out if it is prime.
How do I know if a number is prime?
A prime has exactly two factors, 1 and itself. Check divisors up to its square root: 97 is not divisible by 2, 3, 5 or 7 (√97 ≈ 9.8), so it is prime; 91 is not — it is 7 × 13.
Is 1 a prime number?
No — a prime needs exactly two different factors. The smallest prime is 2, the only even prime.
How many primes are there below 100?
25: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
What are the nearest primes to 100?
97 below and 101 above.
How large a number can it check?
Any whole number up to 1,000,000,000,000,000 (10¹⁵). 1,000,000,007 is prime, for example — a favorite of programmers.
How many primes are there below 1,000 or 1,000,000?
Up to 10, 100, 1,000, 10,000, 100,000 and 1,000,000 there are 4, 25, 168, 1,229, 9,592, 78,498 primes, the values tabulated for the prime counting function in Wolfram MathWorld. They thin out slowly: 25.0% of the numbers up to 100 are prime, 16.8% up to 1,000 and 7.8% up to 1,000,000.
Are there infinitely many primes?
Yes. Euclid’s second theorem shows that the primes never run out (Wolfram MathWorld), so there is no largest one.
How the test works
A prime is a counting number greater than 1 whose only factors are 1 and itself; any other number above 1 is composite, and 1 is neither (OpenStax Prealgebra 2e, section 2.4). MathWorld adds why 1 is excluded: if it were prime, a number could be written as a product of primes in more than one way, since n = n × 1. To test n, divide it by the primes in order and stop when one divides it or the quotient falls below the divisor. That happens at √n, because two factors both above √n would multiply to more than n. Every prime except 2 and 3 has the form 6k ± 1 (MathWorld), so after 2 and 3 the calculator only tries 5, 7, 11, 13, 17, 19 and so on.
Worked example: is 221 prime?
Here √221 ≈ 14.9, so only 2, 3, 5, 7, 11 and 13 need testing. The number 221 is odd, its digits add up to 5 (not a multiple of 3) and it does not end in 0 or 5, so 2, 3 and 5 fail (OpenStax Table 2.10). Then 7 × 31 = 217 and 11 × 20 = 220 fall short by 4 and 1, but 13 × 17 = 221. The calculator answers “No”, shows 221 = 13 × 17 and gives the nearest primes 211 and 223.
Common mistakes
Treating every odd number as prime: 91 = 7 × 13 and 119 = 7 × 17 look prime at a glance. Stopping one prime too early: 121 passes the tests for 2, 3, 5 and 7 and is still composite, since 11 × 11 = 121, so the divisor √n itself must be tried. Assuming that a last digit of 1, 3, 7 or 9 makes a number prime (21, 27, 49 and 77 are not). The calculator works on whole numbers, so a decimal such as 97.9 is cut to 97 before it is tested.
Sources: OpenStax, Prealgebra 2e, section 2.4 “Find Multiples and Factors” (definitions, divisibility tests, prime test); Wolfram MathWorld, “Prime Number” and “Prime Counting Function”. Related tools: factor calculator, LCM and GCF calculator, modulo calculator and factorial calculator. How we check our calculators.