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.

What's the key thing to understand about 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.

What's the key thing to understand about 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.

What should I know about Special Categories of Primes?

What should I know about a Worked Example: GCD and LCM via Prime Factorisation?

As a worked example of using prime factorisation practically, find the GCD and LCM of 84 and 90. Factorising: 84 = 2²×3×7, and 90 = 2×3²×5. The GCD takes the lowest power of every shared prime: for 2, the lower of (2² vs 2¹) is 2¹; for 3, the lower of (3¹ vs 3²) is 3¹. GCD = 2×3 = 6. The LCM takes the highest power of every prime appearing in either number: 2², 3², 5¹, 7¹. LCM = 4×9×5×7 = 1,260. A quick check confirms GCD×LCM equals the product of the two original numbers: 6×1,260 = 7,560, and 84×90 = 7,560 — a useful identity that offers a fast way to find the LCM once the GCD is known (LCM = (a×b)/GCD).

What should I know about the Sieve of Eratosthenes?

For finding all primes up to a reasonably large limit at once, the Sieve of Eratosthenes is far more efficient than testing each number individually by trial division. The method: list every integer from 2 up to the limit, then starting from 2, cross out every multiple of 2 (4, 6, 8, ...), move to the next uncrossed number (3), cross out every multiple of 3, and repeat with each next uncrossed number. Whatever remains uncrossed when the process finishes is exactly the list of primes up to that limit. For primes up to 30: starting with 2 through 30, crossing multiples of 2, then 3, then 5 (since √30≈5.48, no further crossing is needed once the crossing prime exceeds the square root of the limit) leaves 2,3,5,7,11,13,17,19,23,29 — the ten primes below 30. This method's efficiency comes from crossing out many composite numbers at once per pass, rather than individually testing each number's divisors from scratch.