Prime Number Checker

Prime numbers — integers greater than 1 divisible only by 1 and themselves — are the atoms of number theory. Every integer greater than 1 is either prime or can be expressed uniquely as a product of prime numbers (the Fundamental Theorem of Arithmetic). This primality property makes primes foundational in cryptography (RSA encryption's security depends on the computational difficulty of factoring large numbers into primes), computer science (hash functions, random number generation), and mathematics across dozens of specialized areas. Knowing how to determine whether a number is prime — efficiently, for both small and large numbers — is a practical skill with real computational applications.

Fermat's Little Theorem and Probabilistic Tests

For large numbers (hundreds of digits), trial division is computationally infeasible, and even the sieve fails on memory requirements. Probabilistic primality tests provide fast answers with very high confidence. Fermat's Little Theorem: if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). The Fermat primality test checks this for several random values of a — if any fail, p is definitely composite; if all pass, p is probably prime.

The Miller-Rabin primality test is the industry-standard probabilistic test. For each randomly chosen base a: write p-1 = 2ˢ × d (odd d). Compute a^d mod p. If the result is 1 or p-1, this base passes. Otherwise, square it repeatedly up to s times — if it ever reaches p-1, it passes. If none of the squarings reach p-1, p is composite. Each base that passes reduces the probability of false positives by factor 4. With 20 random bases, the probability that a composite number passes all 20 tests is less than 4^(-20) ≈ 10^(-12). Used in SSL/TLS certificate generation, the Miller-Rabin test determines primality of 2048-bit and 4096-bit candidate primes in milliseconds.

Related Calculators

• Factorial Calculator
• Fibonacci Number Calculator

The Trial Division Method

The most straightforward primality test: divide the candidate number n by every integer from 2 up to √n. If no divisor is found, n is prime. If any division yields a remainder of 0, n is composite. Why only up to √n? Because if n = a × b and both a and b are greater than √n, then a × b > √n × √n = n — a contradiction. So any composite number must have at least one factor ≤ √n.

Test whether 97 is prime: √97 ≈ 9.85. Check divisors 2 through 9. 97/2 = 48.5 (not integer). 97/3: 9+7=16, not divisible by 3. 97/4: not integer. 97/5: doesn't end in 0 or 5. 97/6: not integer. 97/7 ≈ 13.86 (not integer). 97/8: not integer. 97/9: 9+7=16, not divisible by 9. No divisors found → 97 is prime.

Optimization: check 2 first, then all odd numbers only (eliminating even composites immediately). Better: check 2 and 3 first, then numbers of the form 6k±1 (since all primes greater than 3 are of this form). This reduces the number of trial divisions by roughly 2/3 compared to checking all odd numbers.

Applications in Cryptography

RSA encryption generates two large prime numbers p and q (each typically 1,024 to 2,048 bits), computes their product n = pq, and bases security on the practical impossibility of factoring n back into p and q. Generating suitable primes: pick a large random odd number, test primality with Miller-Rabin using 20+ bases, repeat until a prime is found. By the Prime Number Theorem, roughly 1 in ln(n) candidates is prime — for a 2048-bit number, about 1 in 1,419 trials succeeds. Testing each candidate takes milliseconds. The whole process of finding two 2048-bit primes takes under a second on modern hardware.

The security assumption: given n = pq (a 2048-bit product), finding p and q is computationally infeasible. The best known factoring algorithms (number field sieve) would take longer than the age of the universe to factor a 2048-bit number on classical computers. But quantum computers running Shor's algorithm could factor such numbers efficiently — which is why post-quantum cryptography research (developing algorithms secure against quantum attacks) has become a major active field. The primality and factorization properties of integers underlie the security of essentially all encrypted internet communication today.

Sieve of Eratosthenes: Finding All Primes Up to n

When you need all primes up to a limit n rather than testing a single number, the Sieve of Eratosthenes is dramatically more efficient. Algorithm: write all integers from 2 to n. Starting with 2, mark all multiples of 2 (4, 6, 8...) as composite. Move to the next unmarked number (3) and mark all its multiples (6, 9, 12...). Continue with 5, 7, 11... until you reach √n. All remaining unmarked numbers are prime.

Primes up to 50: Write 2-50. Mark multiples of 2: 4,6,8,...50. Mark multiples of 3: 9,15,21,27,33,39,45. Mark multiples of 5: 25,35. Mark multiples of 7: 49. (√50 ≈ 7.07, so we stop here.) Remaining primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. That's 15 primes up to 50. The sieve computes all of them in O(n log log n) operations — dramatically faster than running trial division on each number individually.

The Distribution of Primes: Prime Number Theorem

How many primes are there up to n? The Prime Number Theorem states that the number of primes up to n (denoted π(n)) is approximately n / ln(n). Primes up to 1,000: π(1000) ≈ 1000 / 6.91 ≈ 145. Actual count: 168 — a reasonable approximation. Primes up to 1,000,000: π(10⁶) ≈ 10⁶ / 13.8 ≈ 72,464. Actual count: 78,498.

The average gap between primes near n is approximately ln(n). Near 1,000, primes appear roughly every 7 numbers on average. Near 1,000,000, roughly every 14 numbers. Near 10^100 (a googol), roughly every 230 numbers. Primes thin out as numbers get larger, but they never stop — Euclid proved there are infinitely many primes around 300 BC, and that proof remains one of mathematics' most elegant: suppose there are finitely many primes p₁, p₂, ..., pₙ. Form N = (p₁ × p₂ × ... × pₙ) + 1. N is not divisible by any of our listed primes (each gives remainder 1). So N is either prime itself, or has a prime factor not in our list. Either way, our list was incomplete — contradiction. Therefore infinitely many primes exist.