Prime Number Calculator
Check if a number is prime, find the next prime, or list all primes up to any limit.
#p What is a Prime Number?
A prime number is any integer greater than 1 that has exactly two positive divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The number 2 is the only even prime — every other even number is divisible by 2 and therefore composite. Numbers that are not prime (and not 1) are called composite numbers: they have at least one divisor between 1 and themselves.
Prime numbers are the fundamental building blocks of arithmetic. The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a unique product of primes (its prime factorization). For example, 360 = 2³ × 3² × 5. This uniqueness property makes primes central to number theory, cryptography (RSA encryption relies on the difficulty of factoring large numbers into primes), computer science, and pure mathematics.
Testing primality efficiently is a classic computer science problem. The simplest method — trial division — checks all integers from 2 to √n. This works well for numbers up to a few million. For enormous numbers (hundreds of digits), probabilistic tests like Miller–Rabin or deterministic algorithms like AKS are used. This calculator uses trial division, optimized to check only odd divisors after ruling out evenness, giving O(√n) performance.
To generate all primes up to a limit, the Sieve of Eratosthenes is the classical algorithm: mark all integers, then iteratively cross out multiples of each prime starting from 2. It runs in O(N log log N) time and is highly practical for N up to 10 million on modern hardware. This calculator's List mode uses this approach for limits up to 10,000.
📐 Formula & Rules
📖 How to Use This Calculator
Check Prime Mode
List Primes Mode
💡 Example Calculations
Example 1 — Classic Prime: 97
Is 97 prime?
Example 2 — Composite: 91
Is 91 prime?
Example 3 — Large Prime: 999,983
Is 999,983 prime?
Example 4 — List All Primes Up to 50
Find all primes ≤ 50
Frequently Asked Questions
🔗 Related Calculators
What is a prime number?
A prime number is a natural number greater than 1 that has exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13. The number 2 is the only even prime; all other even numbers are divisible by 2 and therefore composite (having more than two divisors).
Is 1 a prime number?
No. 1 is not prime. By the modern definition, a prime must have exactly two distinct positive divisors (1 and itself). Since 1 has only one positive divisor, it is classified as neither prime nor composite. This definition ensures the Fundamental Theorem of Arithmetic works cleanly: every integer ≥ 2 has a unique prime factorization.
How do you check if a number is prime?
To check if n is prime: (1) If n < 2, not prime. (2) If n = 2, prime. (3) If n is even, not prime. (4) Check all odd numbers from 3 up to √n. If any divide n evenly, it is composite; otherwise it is prime. This works because if n has a factor larger than √n, it must also have one smaller than √n.
What are the prime numbers from 1 to 100?
There are 25 primes from 1 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. Use the List mode of this calculator (enter limit = 100) to verify this instantly.
What is a composite number?
A composite number is a positive integer greater than 1 that has at least one positive divisor other than 1 and itself. Examples: 4 = 2×2, 6 = 2×3, 9 = 3×3, 15 = 3×5. Every composite number can be expressed as a product of primes (its prime factorization). The Fundamental Theorem of Arithmetic guarantees this factorization is unique.
What is the smallest prime factor?
The smallest prime factor of a composite number n is the smallest prime that divides n evenly. For even numbers it is always 2. For odd composites, you check 3, 5, 7, … up to √n. Example: smallest prime factor of 91 is 7, since 91 = 7 × 13. Knowing the smallest factor immediately confirms a number is composite.
How many primes are there up to 1,000? Up to 10,000?
There are 168 primes up to 1,000 and 1,229 primes up to 10,000. The density of primes thins out as numbers grow - roughly 1 in ln(n) numbers near n is prime. This is the Prime Number Theorem: π(n) ≈ n / ln(n).
What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes is an ancient algorithm to find all primes up to a limit N. Start with all integers from 2 to N marked as prime. For each prime p, cross out all multiples of p (starting from p²). Repeat until p > √N. The remaining marked numbers are all primes. It runs in O(N log log N) time and is very efficient for N up to a few million.
Are there infinitely many primes?
Yes. Euclid's proof (circa 300 BC): assume there are finitely many primes p1, p2, …, pk. Form Q = p1 × p2 × … × pk + 1. Q is either prime (contradiction) or has a prime factor not in our list (contradiction). Therefore the assumption was wrong, and primes are infinite. Modern research focuses on open problems like the twin prime conjecture and Goldbach's conjecture.
What are twin primes?
Twin primes are pairs of primes that differ by 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), and many more. The twin prime conjecture states there are infinitely many such pairs - it is unproven as of 2025. The largest known twin prime pair has over 388,000 digits.