Prime Number Checker

What Makes a Number Prime?

A prime number is a positive integer greater than 1 with exactly two factors: 1 and itself. Worked through: 7 is prime because its only factors are 1 and 7; 8 is not prime because 1, 2, 4, and 8 all divide it. Two key boundary cases: 2 is the only even prime number (any other even number is divisible by 2, so has 2 as a factor and isn't prime), and 1 is not prime by definition — it has only one factor (itself), violating the 'exactly two' rule. Excluding 1 from the primes isn't arbitrary; it's necessary for the Fundamental Theorem of Arithmetic (unique prime factorisation) to work. The first ten primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — and after 2, all primes are odd. To check whether n is prime by hand, test divisibility by every prime up to √n: if no prime in that range divides n, then n is itself prime. For example, to check whether 97 is prime, test primes up to √97 ≈ 9.85 — so 2, 3, 5, 7. None divide 97, so 97 is prime. You only need to check up to √n because if n had a factor larger than √n, the matching factor (n divided by it) would be smaller than √n and you'd already have found it. Primes thin out as numbers grow (the prime-counting function π(n) grows roughly like n/ln(n)), but they never run out — Euclid proved over 2,000 years ago that there are infinitely many.

Prime Factorisation

Every integer greater than 1 is either prime, or can be expressed as a unique product of primes — that's the Fundamental Theorem of Arithmetic, one of the most important results in number theory. 'Unique' means the factorisation is the same regardless of how you got there (the order of factors can vary, but the prime factors and their counts are fixed). Worked example: 84 = 2 × 42 = 2 × 2 × 21 = 2 × 2 × 3 × 7, written compactly as 2² × 3 × 7. Whatever route you take (84 = 4 × 21 = 4 × 3 × 7 = 2² × 3 × 7, or 84 = 6 × 14 = 2 × 3 × 2 × 7 = 2² × 3 × 7), the prime factorisation comes out the same. The standard method is to repeatedly divide by the smallest prime that divides the number: start with 2, dividing as many times as possible; then 3; then 5; then 7; and so on. Prime factorisation is the basis for finding GCD and LCM efficiently (the GCD is the product of shared prime factors at their lowest powers; the LCM is the product of all prime factors at their highest powers across the inputs). It also reveals number properties: a perfect square has every prime factor appearing an even number of times (36 = 2² × 3² has even powers); a cube has every prime factor appearing in multiples of three. The fundamental theorem ensures that this 'genetic code' of a number is unique, which makes it a powerful analytical tool. This calculator can return the prime factorisation alongside checking primality.

Why Primes Matter

Primes might seem like a mathematical curiosity, but they're the foundation of modern internet security. RSA encryption — used to secure almost every HTTPS connection, banking session, and encrypted message — depends on the difficulty of factoring large numbers into their prime components. A public key consists of two large primes (each typically hundreds of digits long) multiplied together; the resulting number is shared publicly. To decrypt, you need the original primes — but factoring the product back into its primes is computationally infeasible at the sizes used. Multiplying two 1,024-bit primes is fast; factoring the 2,048-bit result is so slow that even the fastest classical computers would take longer than the age of the universe. This asymmetry — easy to multiply, near-impossible to factor — is what makes public-key cryptography work. (Quantum computers could change this, which is why 'post-quantum' cryptography is an active research area.) Beyond cryptography, primes appear in pseudo-random number generators, hash functions, error-correcting codes, and many algorithms in computer science. They're also central to deep mathematics: the Riemann Hypothesis, one of the most famous unsolved problems, is about the distribution of primes. Twin primes (primes differing by 2, like 11 and 13, or 17 and 19), Mersenne primes (of the form 2ⁿ−1), and the search for ever-larger primes drive both theory and computing power. A simple definition — only divisible by 1 and itself — turns out to underpin some of the deepest and most useful mathematics.

Exam Tips and Common Errors

A few habits prevent the most frequent prime-related mistakes. First, remember 1 is not prime and 2 is — these boundary cases trip people up regularly. Second, when checking whether a number is prime by trial division, only test primes up to √n (not up to n, which is wasteful, or up to n/2 unnecessarily); this is faster and the reasoning is sound. Third, all primes except 2 are odd, so once you've ruled out divisibility by 2, you only need to test odd potential factors — halving the work. Fourth, in prime factorisation, work systematically from the smallest prime upward, and check each prime as many times as it divides — 24 = 2 × 12 = 2 × 2 × 6 = 2 × 2 × 2 × 3, written as 2³ × 3 (don't miss repeated factors). Fifth, when finding GCD or LCM via factorisation, take all the primes involved in either number: GCD uses the lowest power of each shared prime; LCM uses the highest power of each prime appearing in any number. Sixth, divisibility shortcuts speed checks: a number is divisible by 2 if its last digit is even; by 3 if its digit sum is divisible by 3; by 5 if it ends in 0 or 5; by 9 if its digit sum is divisible by 9. Seventh, for larger numbers, the sieve of Eratosthenes is much faster than trial division — list integers up to n and cross off multiples of each prime in turn; what remains is prime. Finally, this calculator handles primality testing and factorisation directly, but understanding the underlying logic helps you sanity-check results and tackle harder problems by hand.