Prime Number Checker
Test if a number is prime and see nearby primes, with explanation.
Results
What Is a Prime Number?
A prime number is a natural number greater than 1 that has exactly two distinct divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 is the only even prime. Numbers greater than 1 that are not prime are called composite numbers.
How to Test for Primality
The simplest method: trial division. Divide the number n by every integer from 2 up to √n. If none divide evenly, n is prime. This works because if n has a factor larger than √n, it must also have one smaller than √n.
Special Cases
1 is neither prime nor composite by definition. 2 is the smallest prime and the only even prime. Every prime greater than 2 is odd. Every prime greater than 3 is of the form 6k±1 (but not all such numbers are prime).
The Fundamental Theorem of Arithmetic
Every integer greater than 1 is either a prime or can be uniquely expressed as a product of primes (prime factorization). For example, 60 = 2² × 3 × 5. This uniqueness makes primes the "building blocks" of all integers.
Applications of Prime Numbers
Primes are central to cryptography. RSA encryption relies on the difficulty of factoring large numbers that are the product of two large primes. Hash functions, pseudorandom generators, and error-correcting codes also rely on prime number properties.
Worked Example: Testing Whether 97 Is Prime
Step 1 — Find the square root of 97: √97 ≈ 9.85. We only need to test divisors up to 9.
Step 2 — Test divisibility by each prime up to 9: 2, 3, 5, 7.
97 ÷ 2 = 48.5 (not divisible). 97 ÷ 3 = 32.3... (not divisible). 97 ÷ 5 = 19.4 (not divisible). 97 ÷ 7 = 13.86... (not divisible).
Since no prime up to √97 divides 97, it is prime. 97 is the 25th prime number.
Primes up to 100
| All primes up to 100 | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 |
| 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 |
| 73 | 79 | 83 | 89 | 97 | |||||
Frequently Asked Questions
No. By definition, a prime must have exactly two divisors: 1 and itself. 1 has only one divisor (itself), so it is neither prime nor composite.
Yes. 2 is the smallest prime and the only even prime number. It has exactly two divisors: 1 and 2.
Trial division up to √n works for moderate-sized numbers. For large numbers, probabilistic tests like Miller-Rabin are used. If no integer from 2 to √n divides n, it is prime.
Twin primes are pairs of primes that differ by 2: (3,5), (5,7), (11,13), (17,19), (29,31)... It is unknown whether there are infinitely many twin prime pairs.
RSA encryption uses the product of two large primes as a public key. Factoring the product back into its two prime factors is computationally infeasible for very large primes, making the encryption secure.
Yes. Euclid proved this around 300 BC. His proof: assume there are finitely many primes p₁, p₂, ..., pₙ. Consider the number (p₁ × p₂ × ... × pₙ) + 1. It is not divisible by any of the listed primes, so either it is prime itself or has a prime factor not in the list — contradicting the assumption.
A Mersenne prime is a prime of the form 2ⁿ − 1. Examples: 3 (2²−1), 7 (2³−1), 31 (2⁵−1), 127 (2⁷−1). As of 2024, the largest known Mersenne prime has over 41 million digits. Finding new Mersenne primes is a distributed computing project (GIMPS).