# Sieve of Eratosthenes (Python)

From LiteratePrograms

**This program is a code dump.**

Code dumps are articles with little or no documentation or rearrangement of code. Please help to

**turn it into a literate program**. Also make sure that the source of this code does consent to release it under the CC0 license.

The Sieve of Eratosthenes is an algorithm for rapidly locating all the prime numbers in a certain range of integers. It operates by marking as composite all nontrivial multiples of each prime in sequence until only primes remain unmarked. It is most well-suited to implementation using arrays, which are compact and feature random access.

<<streams.py>>=defstreamfilter (pred, stream):foriinstream:ifpred(i): yield idefints(n):whileTrue: yield n n = n+1<<prime_sieve_streams.py>>=defprimes: nums = ints(2)whileTrue: prime = nums.next() yield primedef curfilter(v, p=prime):return((v % p) != 0) nums = streamfilter (curfilter, ints)

Download code |