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

🤖
AI Insights - Coming Soon!
AI-powered prime number explanations, factorization walkthroughs, and number theory concepts.
⏳ Coming Soon - Stay Tuned!

⚡ 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.