Check if any number up to 10 trillion is prime. Find factors, closest primes, twin prime pairs, next primes, and generate all primes in a range using the Sieve of Eratosthenes.
A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. In other words, a prime cannot be divided evenly by any number other than 1 and the number itself.
The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...
Numbers that are not prime (and greater than 1) are called composite numbers — they have at least one factor other than 1 and themselves. The number 1 is neither prime nor composite — it is a special case in a category of its own.
The definition of prime requires exactly two distinct divisors. The number 1 has only one divisor (itself), so it fails this requirement. Historically, some mathematicians included 1 as prime, but modern mathematics excludes it. The primary reason is the Fundamental Theorem of Arithmetic: every integer greater than 1 has a unique prime factorization. If 1 were prime, this uniqueness would break down (e.g., 6 could be written as 2 × 3 or 1 × 2 × 3 or 1 × 1 × 2 × 3...).
The number 2 is the only even prime. All even numbers greater than 2 are divisible by 2, making them composite. This makes 2 a uniquely important prime — all other primes are odd.
The simplest method: try dividing 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 if n has a factor greater than √n, it must also have a corresponding factor smaller than √n. For example, to test if 97 is prime, you only need to check divisibility by 2, 3, 5, 7 (since √97 ≈ 9.85). None divide 97, so 97 is prime.
To find all primes up to a limit N, the Sieve of Eratosthenes is far more efficient than testing each number individually:
This algorithm has time complexity O(n log log n), making it very fast for generating all primes up to large limits.
For very large numbers, trial division is too slow. The Miller-Rabin test is a probabilistic primality test that can quickly check if a number is prime with very high probability. By using specific deterministic witness sets, it can be made exact for numbers up to at least 3.3 × 10^24 without any probabilistic uncertainty. This is the basis for primality testing in cryptographic applications.
Twin primes are pairs of primes that differ by exactly 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73)... The Twin Prime Conjecture, one of the oldest unsolved problems in mathematics, states that there are infinitely many twin prime pairs. Despite modern computer searches finding twin primes with thousands of digits, no proof exists. The largest known twin primes (as of 2025) have over 500,000 digits each.
The Prime Number Theorem states that the number of primes up to N is approximately N / ln(N). This tells us that primes become less frequent as numbers get larger, but there are infinitely many of them. The average gap between primes near N is approximately ln(N). Near 10, primes are about ln(10) ≈ 2.3 apart on average. Near 1,000,000, the average gap grows to about ln(1,000,000) ≈ 13.8.
| Range | Primes Count | Prime Density |
|---|---|---|
| 1–100 | 25 | 25.0% |
| 1–1,000 | 168 | 16.8% |
| 1–10,000 | 1,229 | 12.3% |
| 1–1,000,000 | 78,498 | 7.8% |
| 1–1,000,000,000 | 50,847,534 | 5.1% |
Mersenne primes are primes of the form 2ⁿ - 1. The first few are: 3 (2²-1), 7 (2³-1), 31 (2⁵-1), 127 (2⁷-1), 8191 (2¹³-1)... The Great Internet Mersenne Prime Search (GIMPS) distributed computing project has found the largest known primes. As of 2024, the largest known prime is 2^136,279,841 - 1, a number with over 41 million digits, discovered in October 2024.
Prime numbers are the foundation of modern cryptography. RSA encryption (used for HTTPS, email encryption, and digital signatures) works by multiplying two large primes p and q to create a public key n = p × q. The security relies on the fact that factoring large numbers into their prime components is computationally infeasible — finding p and q from n when they are hundreds of digits long would take millions of years even with current computers. Typical RSA keys use primes with 1,024 to 4,096 bits (roughly 300 to 1,200 decimal digits).
A Sophie Germain prime is a prime p where 2p + 1 is also prime. Examples: 2 (2×2+1=5), 3 (2×3+1=7), 5 (2×5+1=11), 11 (2×11+1=23). These appear in cryptography (related to safe prime generation for Diffie-Hellman key exchange). Other notable prime types include: Fermat primes (2^(2^n)+1), Wieferich primes, Wilson primes, and prime-generating polynomials like Euler's n² + n + 41 which produces primes for n = 0 to 39.
In the UK, prime numbers are introduced in Key Stage 2 (Years 5–6, ages 9–11) and reinforced in Key Stage 3 and GCSE. Students must know the definition, list primes to 100, test for primality, and apply prime factorization. In the US, prime numbers are covered from Grade 4 (Common Core) through middle school, with prime factorization used for GCF, LCM, and fraction simplification.
No. The number 1 is not prime. By definition, a prime has exactly two distinct positive divisors: 1 and itself. The number 1 has only one divisor (1 itself). Mathematicians specifically exclude 1 from the primes to preserve the Fundamental Theorem of Arithmetic (unique prime factorization of every integer greater than 1).
Yes. 2 is the only even prime. Any even number greater than 2 is divisible by 2, which gives it at least three divisors (1, 2, and itself), making it composite. 2 divides into itself exactly once and into 1 exactly, meeting the definition of prime perfectly.
Twin primes are pairs of prime numbers that differ by 2. Examples: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43). The Twin Prime Conjecture states there are infinitely many such pairs, but this remains unproved despite being one of the most famous open problems in mathematics.
For numbers up to about 10^15, trial division up to √n is feasible. For larger numbers, use the Miller-Rabin primality test or the AKS algorithm. This calculator uses trial division with optimisations (testing only 2, 3, then numbers of form 6k±1) sufficient for most practical purposes.
As of late 2024, the largest known prime is 2^136,279,841 - 1, discovered by GIMPS in October 2024. It has over 41 million digits. All of the largest known primes are Mersenne primes (of the form 2^p - 1 where p itself is prime), discovered through distributed computing projects.
RSA encryption multiplies two large primes (p × q = n) to create a public key. The security relies on the mathematical difficulty of factoring n back into p and q. While multiplying two 300-digit primes takes milliseconds, finding the original primes from their product is believed to require astronomical computing time, securing billions of internet transactions.
An ancient algorithm for finding all primes up to a limit: list all numbers, then repeatedly cross out multiples of each prime starting from 2. Numbers that remain uncrossed are prime. It is highly efficient for finding all primes up to moderate limits (practical up to ~10 million) and is taught in UK and US schools as a systematic method for prime generation.
Yes. Euclid proved this around 300 BCE with a simple proof by contradiction: assume there is a finite list of all primes p1, p2, ..., pn. Consider the number N = (p1 × p2 × ... × pn) + 1. This number is either prime (not in our list) or has a prime factor not in our list. Either way, our list was incomplete — contradiction. Therefore, there must be infinitely many primes.
Results are for educational purposes. This calculator uses trial division and is suitable for numbers up to ~10^13 in reasonable time. For extremely large numbers, use a dedicated primality testing library.