Topic summary
Generating primes
Extracted from the Wikipedia article Generation of primes.
Prime sieves
A prime sieve works by creating a list of all integers up to a desired limit and progressively removing composite numbers (which it directly generates) until only primes are left. This is the most efficient way to obtain a large range of primes; however, to find individual primes, direct primality tests are more efficient. Furthermore, based on the sieve formalisms, some integer sequences (sequence A240673 in the OEIS) are constructed which also could be used for generating primes in certain intervals.