Home / Math / Prime Number Checker
Math 🆓 Free 🔢 Number Theory

🔢 Prime Number Checker

Enter any number to instantly check if it's prime - with a step-by-step divisibility test and prime factorization. Generate a list of all primes in any range using the Sieve of Eratosthenes, or explore the prime distribution visualisation. Includes twin primes, Mersenne primes, and how prime numbers secure the internet.

Is it Prime?

Try:
-
-
-
-

Sieve of Eratosthenes (1–200)

Blue = Prime   Grey = Composite. Click any number to check it.

There are 46 prime numbers between 1 and 200.

Find Primes in a Range

Prime Number Facts

♾️
Infinite Primes
There are infinitely many prime numbers. Euclid proved this around 300 BCE: assume a finite list of all primes, multiply them together and add 1 - the result is either prime or has a prime factor not in the original list. Either way, your list was incomplete!
Primes & Cryptography
Modern internet security (RSA encryption) relies on the fact that multiplying two large primes is easy, but factoring the result is computationally hard. Your bank uses primes with hundreds of digits. Breaking RSA-2048 would take longer than the age of the universe with current computers.
🏆
Largest Known Prime
As of 2024, the largest known prime is 2¹³,⁴⁶⁶,⁹¹⁷ − 1, a Mersenne prime with over 40 million digits! Found by the GIMPS (Great Internet Mersenne Prime Search) project. These primes have the form 2ⁿ − 1 and are discovered using distributed computing.
🌀
The Riemann Hypothesis
The Riemann Hypothesis (1859) predicts the exact distribution of prime numbers along the number line - but it remains unproven. It's one of the Millennium Prize Problems: solve it and win $1 million. The Clay Mathematics Institute has offered this prize since 2000.
👯
Twin Primes
Twin primes are pairs of primes that differ by 2, like (3,5), (11,13), (17,19), (41,43). The Twin Prime Conjecture says there are infinitely many such pairs - but this has never been proven! In 2013, Yitang Zhang proved there are infinitely many prime pairs within 70 million of each other.
🔢
Goldbach's Conjecture
Every even number greater than 2 can be expressed as the sum of two primes. Example: 8 = 3+5, 28 = 11+17. Proposed by Christian Goldbach in 1742, verified up to 4×10¹⁸ by computer, but never proven for all even numbers. One of the oldest unsolved problems in mathematics!
🐚
Primes in Nature
Cicadas emerge from underground every 13 or 17 years - both prime numbers! This is believed to be an evolutionary strategy: by emerging at prime-number intervals, cicadas minimize overlap with predator population cycles (which tend to follow shorter, composite cycles).
2️⃣
The Only Even Prime
2 is the only even prime number. Every other even number is divisible by 2, so it can't be prime. This makes 2 unique - it's sometimes called "the oddest prime" because it's the only even one. All primes greater than 2 are odd.

Prime Number Formulas & Theory

Definition of a Prime Number

A prime number p is a natural number > 1 that has
exactly TWO factors: 1 and itself.

Prime: 2, 3, 5, 7, 11, 13, 17, 19, 23...
Composite: 4=2×2, 6=2×3, 8=2×2×2, 9=3×3...
Special: 1 is NEITHER prime nor composite

Trial Division Algorithm

To check if n is prime, only test divisors up to √n.

isPrime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for i from 3 to √n (step 2):
if n % i == 0: return False
return True

Why √n? If n = a×b and a ≤ b,
then a ≤ √n - so we only need to check up to √n.

Prime Factorization

Every composite number can be uniquely expressed as a product of primes (Fundamental Theorem of Arithmetic).

Algorithm: divide by smallest prime, repeat

Example: 360
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 2³ × 3² × 5

Mersenne Primes

Mersenne primes have the form: Mₙ = 2ⁿ − 1
(where n must itself be prime)

M₂ = 3, M₃ = 7, M₅ = 31, M₇ = 127
M₁₃ = 8191, M₁₇ = 131071

Not all 2ⁿ−1 are prime: M₄ = 15 = 3×5 (composite)
Only 51 Mersenne primes known as of 2024.

Prime Counting Function π(x)

π(x) = number of primes ≤ x

π(10) = 4 (primes: 2,3,5,7)
π(100) = 25
π(1000) = 168
π(10⁶) = 78,498
π(10⁹) = 50,847,534

Prime Number Theorem: π(x) ≈ x / ln(x)

Frequently Asked Questions

A prime number is a natural number greater than 1 with exactly two positive factors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The number 1 is neither prime nor composite - it has only one factor. All natural numbers greater than 1 are either prime or composite (expressible as a product of primes). The Fundamental Theorem of Arithmetic says every integer greater than 1 has a unique prime factorization.
Test divisibility by all integers from 2 up to √n. If none divide n evenly, n is prime. Why only √n? Because factors come in pairs: if a divides n, then n÷a also divides n - and one of each pair is always ≤ √n. Efficient method: test 2, then 3, then all numbers of the form 6k±1 (all primes greater than 3 are in this form - skipping multiples of 2 and 3). This calculator shows each test step by step.
If 1 were prime, the Fundamental Theorem of Arithmetic (unique prime factorization) would break down. Example: if 1 is prime, then 6 = 2×3 = 1×2×3 = 1×1×2×3 - there would be infinitely many factorizations. Excluding 1 preserves unique factorization. Additionally, the definition of prime requires exactly two factors; 1 has only one factor (itself), so it fails the definition.
Yes - 2 is the only even prime number. Every other even number is divisible by 2, giving it a factor other than 1 and itself, making it composite. 2 is sometimes called 'the oddest prime' because it's the only even one. All primes greater than 2 are odd. An interesting consequence: all prime pairs (twin primes, etc.) with both primes greater than 2 must be odd numbers, giving them specific structural forms.
An ancient Greek algorithm (c. 240 BCE) to find all primes up to n: list all numbers from 2 to n. Starting at 2, mark all multiples of 2 as composite. Move to the next unmarked number (3), mark its multiples. Continue for each unmarked number up to √n. All remaining unmarked numbers are prime. It's efficient because each number is marked at most once per prime factor. Still one of the fastest algorithms for finding all primes in a range.
Twin primes are pairs of primes differing by exactly 2: (3,5), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73). The Twin Prime Conjecture states there are infinitely many such pairs - but this remains unproven despite centuries of effort. In 2013, Yitang Zhang proved there are infinitely many prime pairs with gap ≤ 70,000,000 - subsequently reduced to a gap ≤ 246. Solving the Twin Prime Conjecture exactly is one of the great open problems in mathematics.
RSA encryption - which protects most internet traffic (HTTPS, banking, email) - relies on the asymmetry between multiplication and factoring. Multiplying two large primes (each hundreds of digits) is trivially fast. But given only the product, finding the original two primes ('integer factorization') is computationally infeasible for large numbers with current technology and known algorithms. This asymmetry is the mathematical trapdoor securing your bank, email, and every 'https://' page you visit. Every RSA key includes a large semiprime (product of two primes).
Mersenne primes have the form 2ⁿ − 1. Named after Marin Mersenne (1588–1648). The first few: 3 (2²−1), 7 (2³−1), 31 (2⁵−1), 127 (2⁷−1), 8191 (2¹³−1). Only 51 are known as of 2025. The largest known prime in the world is always a Mersenne prime - the current record is 2^136,279,841 − 1 (over 41 million digits), found by GIMPS (Great Internet Mersenne Prime Search), a distributed computing project anyone can join. The largest known primes are Mersenne primes because there's an efficient test called the Lucas-Lehmer primality test that only works for Mersenne numbers.

First 30 Primes

Related Calculators

🔢 LCM & GCF Calculator Scientific Calculator 💥 Exponent Calculator ➗ Fraction Calculator

Share

Prime Number Checker - How Primality Testing Works and Why Primes Matter

Prime numbers are the atoms of arithmetic - the irreducible building blocks from which all other integers are constructed. Every composite number is just a unique product of primes. This fundamental fact, called the Fundamental Theorem of Arithmetic, underlies everything from elementary factoring to modern cryptography. Understanding how to identify primes - and why the problem gets dramatically harder for large numbers - is one of the most fascinating areas of mathematics.

The primality test shortcut: To check if n is prime, only test divisors up to √n. Why? Because factors come in pairs: if a divides n, then n÷a also divides n. For n = 100: if 4 divides 100, so does 25. The smaller factor in each pair is always ≤ √100 = 10. Testing all the way to n is unnecessary - √n is the boundary.

Different Types of Special Primes

Twin Primes and Prime Pairs

  • Twin primes: Pairs differing by 2. (3,5), (11,13), (17,19), (29,31), (41,43), (71,73)
  • Twin Prime Conjecture: There are infinitely many twin prime pairs - still unproven, one of mathematics' great open questions
  • Cousin primes: Differ by 4: (3,7), (7,11), (13,17)
  • Sexy primes: Differ by 6: (5,11), (7,13), (11,17)
  • All prime pairs above (3,5) are of the form (6k−1, 6k+1)

Special Prime Forms

  • Mersenne primes (2ⁿ−1): 3, 7, 31, 127, 8191... Largest known primes are always Mersenne primes. Found by GIMPS distributed computing project.
  • Fermat primes (2^(2ⁿ)+1): 3, 5, 17, 257, 65537. Only 5 known - no new ones found since Euler.
  • Palindromic primes: Same forwards and backwards: 11, 101, 131, 151, 181.
  • Safe primes (2p+1): Used in cryptographic key generation.

The Sieve of Eratosthenes - The Ancient Algorithm That Still Works

The Sieve of Eratosthenes, invented by the Greek mathematician Eratosthenes around 240 BCE, is one of the oldest known algorithms - and it remains one of the most efficient ways to find all primes up to a given limit. The method:

  1. List all integers from 2 to n
  2. Starting at 2 (the first prime), mark all multiples of 2 as composite: 4, 6, 8, 10...
  3. Move to the next unmarked number (3 - it's prime), mark all its multiples: 6, 9, 12, 15...
  4. Move to the next unmarked number (5), mark its multiples: 10, 15, 20, 25...
  5. Repeat until you've processed all numbers up to √n
  6. All remaining unmarked numbers are prime

Why stop at √n? Because any composite number ≤ n must have a prime factor ≤ √n. So after processing all primes up to √n, all remaining unmarked numbers must be prime. The Sieve tab above implements this for any range you choose.

Prime Numbers and Internet Security - How RSA Encryption Works

The security of most internet communication - HTTPS, banking, email encryption, digital signatures - relies directly on a property of prime numbers: multiplying two large primes is trivially fast, but factoring the product back into those two primes is computationally infeasible.

In RSA encryption: choose two large primes p and q (each with hundreds of digits). Compute n = p × q. The public key includes n; the private key uses p and q separately. Encrypting data uses n (easy - just multiplication). Decrypting requires knowing p and q - and no known algorithm can factor a 2,048-bit number in any reasonable time on current hardware.

The asymmetry between multiplication (fast) and factoring (slow) is the mathematical trapdoor that secures modern cryptography. Every time you see "https://" in a browser, prime numbers are protecting your data.

Famous Unsolved Problems in Prime Number Theory

  • Goldbach's Conjecture (1742): Every even integer greater than 2 is the sum of two primes. Verified for all even numbers up to 4 × 10¹⁸, but never proven universally.
  • Twin Prime Conjecture: There are infinitely many pairs of primes that differ by 2. Partially proven by Yitang Zhang in 2013, who showed infinitely many pairs with gap ≤ 70,000,000 (later reduced to 246).
  • Riemann Hypothesis (1859): All non-trivial zeros of the Riemann zeta function lie on the critical line Re(s) = 1/2. Directly connected to the distribution of primes. One of the Millennium Prize Problems with a $1 million reward.
  • Are there infinitely many Mersenne primes? Unknown. Only 51 are known as of 2025.

How this calculator works, and where the numbers come from

The Prime Number Checker applies the standard formula for this calculation to the values you enter and updates the result as you type. The calculation itself happens in your browser, and the page explains the method so you can check any result by hand.

Please note: Results are provided for general information and are calculated from the values you enter.

Sources and further reading

Last reviewed: by the CalcQube Editorial Team. See our editorial policy for how we build and check calculators, or report an error.