Prime Number Finder
Check whether any whole number is prime, or list every prime in a range. The checker handles numbers up to 1,000,000,000,000,000 using Miller-Rabin primality testing. The range lister uses the Sieve of Eratosthenes and supports spans up to 10,000 numbers.
Notes
What Is a Prime Number?
A prime number is a whole number greater than 1 that has exactly two positive divisors: 1 and itself. Numbers with more than two divisors are called composite numbers. The number 1 is special — it is neither prime nor composite by mathematical convention.
| Number | Divisors | Type |
|---|---|---|
| 1 | 1 | Neither |
| 2 | 1, 2 | Prime |
| 3 | 1, 3 | Prime |
| 4 | 1, 2, 4 | Composite |
| 5 | 1, 5 | Prime |
| 12 | 1, 2, 3, 4, 6, 12 | Composite |
How to Check if a Number Is Prime
The simplest method is trial division: divide the number n by every integer from 2 up to √n. If none divide evenly, n is prime. You only need to test up to √n because any factor larger than √n must be paired with one smaller than √n.
The Sieve of Eratosthenes
To find all primes up to a limit N, the Sieve of Eratosthenes is the classic algorithm. Start by listing all numbers from 2 to N. Mark 2 as prime, then cross out all its multiples. Move to the next unmarked number (3), mark it prime, cross out its multiples. Repeat until √N. All remaining unmarked numbers are prime.
- Write all integers from 2 to N.
- Start with p = 2 (smallest prime).
- Cross out all multiples of p starting from p².
- Find the next number not yet crossed out — that is the next prime.
- Repeat from step 3 until p > √N.
- All surviving numbers are prime.
Prime Number Facts
- 2 is the only even prime number.
- All other even numbers are composite (divisible by 2).
- There are infinitely many prime numbers (proved by Euclid, ~300 BC).
- Prime numbers become less frequent as numbers grow larger, but they never stop.
- The largest known prime (as of 2024) has over 41 million digits.
- Every integer greater than 1 can be expressed as a unique product of primes — the Fundamental Theorem of Arithmetic.
- Prime Number Notes – Definitions & Algorithms — Deep dive into primality testing and the sieve
- Prime Number Formula — Trial division, sieve complexity, and Miller-Rabin
Frequently Asked Questions
Is 1 a prime number?
No. By mathematical convention, 1 is neither prime nor composite. A prime must have exactly two distinct positive divisors (1 and itself), but 1 only has one divisor.
Is 2 a prime number?
Yes. 2 is the only even prime number. All other even numbers are divisible by 2, giving them at least three divisors (1, 2, and themselves), making them composite.
What is the largest number this tool can check?
The primality checker handles numbers up to 1,000,000,000,000,000 (10¹⁵) using Miller-Rabin testing. The range lister uses the Sieve of Eratosthenes and supports spans up to 10,000 numbers with a maximum value of 100,000,000.
What are prime factors?
Prime factors are the prime numbers that multiply together to produce the original number. For example, the prime factorization of 60 is 2 × 2 × 3 × 5. Every composite number has a unique prime factorization (Fundamental Theorem of Arithmetic).
Why are prime numbers important?
Primes are the building blocks of all integers. They are also the foundation of modern cryptography — RSA encryption relies on the difficulty of factoring very large numbers that are products of two large primes.