Generate sequential lists of prime numbers up to a specified limit or range. Export lists to text files.
Prime numbers are positive integers greater than 1 that have no divisors other than 1 and themselves: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... The fundamental theorem of arithmetic states that every integer greater than 1 has a unique prime factorization. This makes primes the atomic building blocks of all integers and gives them extraordinary importance across number theory, cryptography, and computer science.
This generator lists all primes up to a specified bound using the Sieve of Eratosthenes — an ancient algorithm attributable to the Greek mathematician Eratosthenes of Cyrene (276–194 BCE). The algorithm marks composite numbers by iteratively eliminating multiples of each prime, leaving only primes unmarked. The sieve runs in O(n log log n) time — nearly linear — making it highly efficient for enumerating primes up to millions.
The Sieve algorithm begins with a boolean array of size n+1, initially all true. Starting from 2, each unmarked number is prime; all its multiples (starting from p²) are marked composite. The optimization of starting from p² (rather than 2p) is valid because all smaller multiples were already marked by smaller primes. After processing all primes up to √n, every remaining unmarked index is prime.
Segmented sieve variants handle ranges larger than memory can hold by processing √n-sized segments. The wheel factorization pre-marks multiples of small primes (2, 3, 5) to reduce constant factors. For extremely large ranges, probabilistic primality tests like Miller-Rabin and deterministic AKS are used instead of enumeration sieves.
The prime number theorem (PNT) describes the asymptotic density of primes: the number of primes below n, denoted π(n), is approximately n/ln(n). More precisely, π(n) ~ Li(n) = ∫₂ⁿ dt/ln(t). This means primes become progressively rarer as numbers grow larger — about 4.3% of numbers near 10,000 are prime, but only 1.4% near 10 million.
Prime gaps — the differences between consecutive primes — vary irregularly. The twin prime conjecture (unproven) states there are infinitely many prime pairs differing by 2 (like 11,13 and 17,19). Bertrand's postulate (proven) guarantees there is always at least one prime between n and 2n for n > 1. The Riemann hypothesis — connecting prime distribution to zeros of the Riemann zeta function — remains the most famous unsolved problem in mathematics.
Create a boolean array of size n+1 (all true). For each number p from 2 to √n: if p is still marked true (prime), mark all multiples of p starting from p² as false (composite). After completing this pass, every index still marked true is prime. Time complexity: O(n log log n). Space: O(n).
No. By definition, prime numbers must have exactly two distinct positive divisors: 1 and themselves. The number 1 has only one divisor (itself), so it is neither prime nor composite. This exclusion is necessary for the fundamental theorem of arithmetic — unique prime factorization — to hold true.
There are infinitely many prime numbers. Euclid's proof (c. 300 BCE) is elegant: assume a finite list of all primes p₁,p₂,...,pₙ; form the number N = p₁×p₂×...×pₙ + 1. N is either prime (not in our list) or has a prime factor not in our list (since no listed prime divides N evenly). Either way, a prime outside our list exists — contradiction.
Twin primes are prime pairs that differ by exactly 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43)... The twin prime conjecture, unproven since ancient Greece, states there are infinitely many twin prime pairs. In 2013, Yitang Zhang proved there are infinitely many prime pairs within 70 million of each other — subsequently reduced to 246.
RSA encryption relies on the difficulty of factoring large numbers that are products of two large primes. Multiplying two 2048-bit primes takes milliseconds, but factoring the product is computationally infeasible with current algorithms (estimated more energy than exists in the observable universe for sufficiently large primes). Elliptic curve cryptography also uses prime fields.