🔍 🔍 Prime Number Checker: What Are Prime Numbers and How to Test Them

Prime numbers are the building blocks of all integers — every whole number greater than 1 either is prime or can be uniquely expressed as a product of primes. This "Fundamental Theorem of Arithmetic" gives primes their central importance in mathematics. And beyond pure math, prime numbers are the foundation of modern cryptography — the RSA encryption that secures online banking, email, and e-commerce depends entirely on the difficulty of factoring large primes.

What is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two distinct factors: 1 and itself.

• 2 is prime: factors are 1 and 2 only (the only even prime)
• 7 is prime: factors are 1 and 7 only
• 9 is NOT prime: factors are 1, 3, and 9 (3 × 3 = 9)
• 1 is NOT prime: by definition, a prime must have exactly two distinct factors

The first 20 prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

How to Test if a Number is Prime: Trial Division

The most straightforward primality test is trial division:

1. If n ≤ 1: not prime
2. If n = 2: prime
3. If n is even (and n ≠ 2): not prime
4. Test division by all odd numbers from 3 up to √n
5. If any divide evenly: not prime. If none do: prime.

Why only up to √n? If n has a factor larger than √n, it must also have a corresponding factor smaller than √n. So if no factor is found up to √n, there are no factors at all.

Example: Is 97 prime?

• √97 ≈ 9.85, so test divisibility by 3, 5, 7 only
• 97 ÷ 3 = 32.33... (not exact)
• 97 ÷ 5 = 19.4 (not exact)
• 97 ÷ 7 = 13.86... (not exact)
• No exact divisors found → 97 is prime

Example: Is 91 prime?

• √91 ≈ 9.54, so test 3, 5, 7
• 91 ÷ 7 = 13 exactly → 91 is NOT prime (91 = 7 × 13)

This is a famous "prime-looking" number that catches many people out — it looks prime but factors as 7 × 13.

The Sieve of Eratosthenes

To find all primes up to a number N efficiently, the ancient Sieve of Eratosthenes works by elimination:

1. Write all integers from 2 to N
2. Starting at 2, cross out all multiples of 2 (4, 6, 8...)
3. Move to the next uncrossed number (3), cross out all its multiples (9, 15, 21...)
4. Repeat for 5, 7, 11... up to √N
5. All remaining uncrossed numbers are prime

This finds all primes up to N in O(N log log N) time — much more efficient than testing each number individually.

Prime Factorization: Every Number's Unique Fingerprint

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime or can be expressed as a unique product of primes:

• 12 = 2² × 3
• 60 = 2² × 3 × 5
• 360 = 2³ × 3² × 5
• 100 = 2² × 5²

To find the prime factorization: divide by 2 until odd, then try 3, 5, 7... up to √n.

Example: Factor 84 → 84÷2=42 → 42÷2=21 → 21÷3=7 → 7 is prime → 84 = 2² × 3 × 7

Notable Types of Primes

• Twin primes: Pairs differing by 2: (3,5), (5,7), (11,13), (17,19), (29,31)... Whether infinitely many twin primes exist is an unsolved problem in mathematics.
• Mersenne primes: Of the form 2ᵖ − 1 (where p is prime): 3, 7, 31, 127, 8191... The largest known primes are Mersenne primes — the current record (as of 2024) has over 41 million digits.
• Fermat primes: Of the form 2^(2ⁿ) + 1: 3, 5, 17, 257, 65537. Only five are known.
• Primorial primes: Related to products of consecutive primes.

Why Primes Matter: RSA Cryptography

Modern internet security relies on one fundamental property of prime numbers: it is easy to multiply two large primes together, but computationally infeasible to reverse the process (factoring the result back into primes) when the primes are sufficiently large.

RSA encryption works roughly as follows:

1. Choose two very large primes p and q (each 1,000+ digits long)
2. Compute n = p × q (easy — just multiply)
3. n becomes part of your public key; p and q remain secret
4. Anyone can encrypt a message using n, but only the holder of p and q can decrypt it

Factoring a 2,048-bit RSA number would take longer than the current age of the universe on classical computers. This mathematical asymmetry — easy to multiply, hard to factor — is what protects online banking, messaging, and e-commerce globally.

Quick Reference: Prime Patterns

• All primes except 2 are odd
• All primes except 5 do not end in 0, 2, 4, 5, 6, or 8
• Numbers ending in 1, 3, 7, or 9 might be prime (but aren't necessarily)
• A number is composite if divisible by any prime up to its square root
• There are infinitely many prime numbers (Euclid's proof, ~300 BC)