Generate all prime numbers up to a given limit using the Sieve of Eratosthenes.
The Sieve of Eratosthenes is one of the oldest and most efficient algorithms for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime starting from 2. Numbers remaining unmarked after all passes are prime. Its time complexity is O(n log log n), making it practical for limits up to about 10 million in a browser environment.
Sieve complexity
Time ≈ O(n × log(log(n))); Space = O(n)
The sieve allocates an array of size n. Beyond 10 million entries, memory use and computation time can freeze a browser tab. For larger searches, use a segmented sieve in a native application.
Start with all numbers 2 to n marked as candidates. Take the smallest unmarked number (2), mark all its multiples as composite, then advance to the next unmarked number and repeat. Every number that is never crossed off is prime.