Prime Number Calculator
Check, Factorize & List Primes
Quick examples
Maximum: 100,000
Enter a number to check if it is prime, or switch to List mode to list all primes up to N.
Result
Ad · 300x250
Prime Numbers Properties & Significance
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23... 2 is the only even prime. There are infinitely many primes, proved by Euclid around 300 BC.
By the Fundamental Theorem of Arithmetic, every integer greater than 1 is either prime or can be expressed uniquely as a product of primes. This makes primes the fundamental building blocks of all integers.
How to Check if Prime
Test divisibility by all integers from 2 up to √n. If none divide evenly, n is prime. Example: is 97 prime? √97 ≈ 9.8. Test 2, 3, 5, 7. None divide 97. Yes, 97 is prime.
Sieve of Eratosthenes
To find all primes up to n: list numbers 2 to n, mark multiples of each prime as composite. Numbers that remain unmarked are prime. Efficient for finding primes in ranges.
Prime Factorization
Every composite number = unique product of primes. 360 = 2³ × 3² × 5. Used for GCF, LCM, simplifying fractions, and cryptography.
Primes in Cryptography
RSA encryption (used in HTTPS) relies on the difficulty of factoring the product of two large primes. A 2048-bit RSA key uses primes each about 300 digits long.
Ad · 728x90
Prime Number Questions
What is a prime number?+
A prime number is a natural number greater than 1 that can only be divided evenly by 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The number 1 is not prime (by definition). 4 is not prime because 4 = 2×2. 2 is the only even prime; all other even numbers are divisible by 2 and therefore composite.
How do I check if a number is prime?+
Test divisibility by all integers from 2 up to the square root of the number. If any divide evenly, it is composite. If none do, it is prime. Example: is 127 prime? √127 ≈ 11.3. Test divisibility by 2, 3, 5, 7, 11. 127 is not divisible by any of these. Therefore 127 is prime. You only need to test up to √n because if n has a factor larger than √n, it must also have one smaller than √n.
What is prime factorization?+
Every composite number can be expressed as a unique product of prime numbers. This is the Fundamental Theorem of Arithmetic. Examples: 12 = 2² × 3. 60 = 2² × 3 × 5. 360 = 2³ × 3² × 5. To find it: divide by the smallest prime (2) repeatedly until it no longer divides, then try 3, 5, 7, etc. Prime factorization is used to find GCF and LCM, simplify fractions, and is the basis of RSA encryption.
Are there infinitely many prime numbers?+
Yes. Euclid proved this around 300 BC with an elegant proof: assume there are finitely many primes p1, p2, ..., pk. Form N = (p1 × p2 × ... × pk) + 1. N is either prime (contradicting our assumption) or has a prime factor not in our list (also a contradiction). Therefore infinitely many primes exist. They become less frequent among larger numbers but never stop entirely.
What is the Sieve of Eratosthenes?+
An ancient algorithm (Eratosthenes of Cyrene, ~240 BC) for finding all primes up to n. Method: (1) List all integers from 2 to n. (2) Starting with p=2, mark all multiples of p (except p itself) as composite. (3) Find the next unmarked number — this is the next prime. (4) Repeat until p² > n. All remaining unmarked numbers are prime. It is efficient because you start crossing out at p² (smaller multiples have already been handled).
What is a composite number?+
A composite number is a natural number greater than 1 that is NOT prime. It has at least one factor other than 1 and itself. Examples: 4 (=2×2), 6 (=2×3), 8 (=2^3), 9 (=3^2), 10 (=2×5). The number 1 is neither prime nor composite. Every positive integer is exactly one of: prime, composite, or the number 1. There are infinitely many composite numbers just as there are infinitely many primes.
What are twin primes?+
Twin primes are pairs of prime numbers that differ by exactly 2. Examples: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73). The Twin Prime Conjecture states there are infinitely many twin prime pairs, but this has not been proved. As of 2016, the largest known twin prime pair has over 388,000 digits each. Twin primes become increasingly rare among larger numbers but appear to never stop.
Why is 1 not a prime number?+
By modern definition, primes must be greater than 1. If 1 were prime, the Fundamental Theorem of Arithmetic (every number has a unique prime factorization) would break down: 12 could be written as 2²×3, or 1×2²×3, or 1²×2²×3, etc. — infinitely many factorizations. Excluding 1 preserves uniqueness. This is a definitional choice made for mathematical convenience, not an arbitrary rule.
How are prime numbers used in cryptography?+
RSA encryption (used in HTTPS, TLS, digital signatures) relies on a simple asymmetry: multiplying two large primes is computationally easy, but factoring their product back into primes is computationally infeasible. A 2048-bit RSA key uses two primes each roughly 300 decimal digits long. Their product (the public key) has 600 digits. Current computers would need billions of years to factor it. This asymmetry underpins secure internet communication.
What is the largest known prime number?+
As of 2024, the largest known prime is 2^136,279,841 − 1, a Mersenne prime with over 41 million digits, discovered in October 2024 by Luke Durant using the GIMPS (Great Internet Mersenne Prime Search) distributed computing project. Mersenne primes have the form 2^p − 1 where p itself is prime. Not all such numbers are prime, but all the largest known primes are Mersenne primes because they are especially efficient to test with the Lucas-Lehmer primality test.