Prime Number Calculator

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and onward forever. Any number above 1 with some other divisor is composite. 2 is the only even prime, and the reason is almost too simple to feel like mathematics: every other even number has 2 as a divisor, which is already a third divisor beyond 1 and itself. That makes 2 the odd one out in the most literal sense — it is the only prime that is not odd. Every prime after it must be odd, which is the first and cheapest shortcut in any primality test. Small composites hide in plain sight. 91 looks prime — it is odd, it does not end in 5, and its digits do not sum to a multiple of 3 — but 91 = 7 × 13. 57 catches people the same way; it is 3 × 19. Eyeballing is not a test.

This is not a technicality or a matter of taste. Admitting 1 as a prime would break the single most useful fact in elementary number theory. The fundamental theorem of arithmetic says every whole number above 1 factors into primes in exactly one way, ignoring the order of the factors. 60 is 2 × 2 × 3 × 5, and there is no other prime factorization of 60 anywhere. Now suppose 1 were prime. Then 60 would also be 1 × 2 × 2 × 3 × 5, and 1 × 1 × 2 × 2 × 3 × 5, and so on without end. Uniqueness would collapse instantly, and every theorem resting on it would need an awkward clause excluding 1. Defining primes to start at 2 keeps the theorem clean. So 1 is neither prime nor composite. It sits in its own category — the multiplicative unit, the number that changes nothing when you multiply by it. Zero and negative numbers are likewise outside the definition, which begins at 2.

To check whether 97 is prime, you do not need to try dividing by all 95 numbers between 2 and 96. You only need the divisors up to √97 ≈ 9.85, which means 2, 3, 5 and 7. Four divisions settle it. The argument is short. If n = a × b with both factors bigger than √n, then their product would exceed √n × √n = n, which is impossible. So any composite number must have a factor at or below its square root. Find nothing there and there is nothing to find above it either. The saving is enormous and it grows. For a six-digit number you check a few hundred candidates instead of hundreds of thousands. Layer on the fact that you can skip every even divisor after 2, and the work halves again — which is exactly what this calculator does: it tests 2, then steps through odd divisors only while i × i ≤ n. One further refinement: past 3, every prime has the form 6k ± 1, so you can step in that pattern and skip two thirds of the candidates. For the very large numbers used in cryptography, trial division stops being viable at all and probabilistic tests take over.

Factoring a number into primes is the closest thing arithmetic has to reading a chemical formula: it tells you what a number is made of, and most questions about it become easy once you know. With 60 = 2² × 3 × 5 and 18 = 2 × 3² in front of you, the greatest common factor is what they share — the lowest power of each common prime, 2 × 3 = 6 — and the least common multiple is the highest power of every prime that appears, 2² × 3² × 5 = 180. That is also how you find a common denominator when adding fractions, and how you reduce a fraction to lowest terms. The factorization also hands you the divisor count for free. Add one to each exponent and multiply: 60 has (2+1)(1+1)(1+1) = 12 divisors, and indeed 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 and 60 are exactly twelve numbers. And it is the basis of public-key cryptography. Multiplying two large primes together is instant; recovering those primes from the product is, as far as anyone has publicly demonstrated, computationally infeasible at the sizes used in practice. The entire asymmetry is that one direction is easy and the other is not.

A proof recorded in Euclid's Elements shows there are infinitely many primes, and it is short enough to hold in your head. Suppose the primes were a finite list. Multiply them all together and add 1. The resulting number leaves a remainder of 1 when divided by every prime on the list, so no listed prime divides it — meaning it is either prime itself or has a prime factor missing from the list. Either way the list was incomplete, and no finite list can ever be complete. They do, however, thin out. Among the first ten numbers, four are prime; among the first hundred, twenty-five are. The prime number theorem makes this precise: near a number x, roughly 1 in ln(x) numbers is prime. Around a billion that is about one in twenty-one, and around a trillion about one in twenty-eight. Thinning is not the same as stopping. Arbitrarily long stretches with no primes at all exist — the numbers from n! + 2 to n! + n are all composite, giving a gap of any length you care to name — and yet primes keep appearing beyond every gap. That is why the "next prime" this calculator reports is always guaranteed to exist, however far it has to search.