Sieve of Eratosthenes (Python)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Alice ML | Bash | C++ | Forth | Haskell | Java | Python | Python, arrays | Scala

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 MIT or public domain 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>>=
def streamfilter (pred, stream):
    for i in stream:
	if pred(i):
	    yield i
def ints(n):
    while True:
	yield n
	n = n+1
<<prime_sieve_streams.py>>=
def primes:
    nums = ints(2)
    while True:
	prime = nums.next()
	yield prime
	def curfilter(v, p=prime):
	    return ((v % p) != 0)
	nums = streamfilter (curfilter, ints)
Download code
Retrieved from "http://literateprograms.org/Sieve_of_Eratosthenes_%28Python%29"
Views