Prime Number Checker

Prime numbers have exactly two divisors: 1 and themselves.

The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Primes are the building blocks of all integers.

Every integer > 1 can be uniquely expressed as a product of primes.

For example, 60 = 2² × 3 × 5.

This is fundamental in mathematics and cryptography.

To check if a number n is prime, test whether any integer between 2 and the square root of n divides it evenly; if none does, n is prime.

First handle small cases:

• numbers below 2 are not prime
• 2 and 3 are prime
• any even number above 2 is composite

Then test odd divisors up to √n, because divisors always come in pairs whose smaller member cannot exceed the square root.

For example, checking 97 only requires testing 3, 5, and 7 (since √97 ≈ 9.85), and none divide it, so 97 is prime. Wolfram MathWorld describes this as trial division, the most direct primality test.

The square root method means you only need to test potential divisors up to √n rather than all the way up to n.

The reason is that if n = a × b, then at least one of the factors a or b must be less than or equal to √n; otherwise their product would exceed n. So if no factor is found below √n, no larger factor exists either.

This dramatically reduces work: checking whether 9,973 is prime requires testing divisors only up to about 99, not nearly 10,000.

Khan Academy uses this pairing argument to explain why trial division stops at the square root, making manual primality checking practical.

The Sieve of Eratosthenes finds all primes up to a limit N by repeatedly marking the multiples of each prime as composite.

Start with a list of integers from 2 to N. Take 2, mark 4, 6, 8, ... as composite; move to the next unmarked number, 3, and mark 6, 9, 12, ...; continue with 5, 7, and so on. Numbers that remain unmarked are prime.

Applied up to 30, the sieve leaves 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Named after the Greek mathematician Eratosthenes of Cyrene, this algorithm (documented by Encyclopaedia Britannica) is one of the oldest and most efficient ways to list primes in a range.

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, apart from the order of the factors.

For example, 360 = 2³ × 3² × 5, and no other combination of primes multiplies to 360. This uniqueness is why primes are called the building blocks of the integers.

According to Wolfram MathWorld, this theorem underpins prime factorization, greatest common divisor computation, and modular arithmetic.

Our calculator uses it when it factors a number, guaranteeing the prime decomposition it returns is the only possible one.

Twin primes are pairs of primes that differ by exactly 2, such as (3, 5), (5, 7), (11, 13), (17, 19), and (29, 31).

The gap between consecutive primes generally grows as numbers get larger, though twin primes keep appearing. Whether infinitely many twin primes exist is the famous Twin Prime Conjecture, still unproven.

The On-Line Encyclopedia of Integer Sequences (OEIS) catalogs the lower members of twin prime pairs in sequence A001359.

Understanding prime gaps helps explain why primes become sparser: near one million, primes are spaced roughly 14 apart on average, a trend described by the Prime Number Theorem in the NIST Digital Library of Mathematical Functions.

Prime numbers power modern cryptography, especially RSA encryption, which secures online banking, HTTPS websites, and digital signatures. RSA relies on the fact that multiplying two large primes is easy, but factoring the product back into those primes is computationally hard.

Beyond security, primes appear in:

• hash table sizing (prime-length tables reduce collisions)
• pseudo-random number generation
• error-correcting codes
• cicada life cycles that evolved around prime-numbered years to avoid predators

Britannica notes that prime factorization also simplifies fractions and computes least common multiples. This calculator supports these tasks by factoring numbers and generating primes for algorithm design and math homework alike.

A prime number has exactly two distinct positive divisors, 1 and itself, while a composite number has more than two divisors.

For example, 13 is prime (divisors 1 and 13), and 12 is composite (divisors 1, 2, 3, 4, 6, 12). The number 1 is neither prime nor composite, because it has only one divisor.

This convention keeps the Fundamental Theorem of Arithmetic clean: if 1 counted as prime, factorizations would no longer be unique since you could insert any number of 1s.

Encyclopaedia Britannica and Khan Academy both stress this distinction, which is why our tool labels 1 separately from primes and composites.

Mersenne primes are primes of the form 2^p − 1, where the exponent p is itself prime; examples include 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1), and 127 (2⁷ − 1).

Not every prime exponent yields a prime, however: 2¹¹ − 1 = 2047 = 23 × 89 is composite.

Mersenne primes matter because a fast test called the Lucas-Lehmer test makes them easier to verify than arbitrary numbers, so the largest known primes are almost always Mersenne primes with tens of millions of digits.

The Great Internet Mersenne Prime Search (GIMPS) coordinates volunteers to discover them. OEIS sequence A000668 lists known Mersenne primes.

• The most common mistake is treating 1 as prime; it is not, because a prime must have exactly two divisors.
• Another error is forgetting that 2 is the only even prime, so people wrongly skip it or wrongly assume other even numbers might be prime.
• A third mistake is stopping trial division too early or too late: you must test all divisors up to √n, not just a few small ones.
• People also confuse prime factorization with listing all factors; 12 has factors 1, 2, 3, 4, 6, 12 but a prime factorization of only 2² × 3.
• Finally, assuming every number of the form 6k ± 1 is prime is false; 25 = 6(4) + 1 is composite.