Python implementation of sieve of Eratosthenes

Lazy functional programming languages can support infinite data structure that contains infinite number of elements. You can define your computation on the infinite data structure. Since the evaluation is lazy, the actual computation will be delayed until it is needed. Some algorithms can be very naturally implemented with this feature.

Python is not a lazy programming language but we can simulate this behavior using generator.

def int2():
    x = 2
    while True:
        yield x
        x = x + 1

int2 is a generater that produces all integers greater than 1.

def filter(gen):
    x = gen.next() #take the first element
    yield x
    while True:
        y = gen.next()
        if y % x != 0: yield y

filter takes a generator as input, and converts it into another generator by filtering out any number that is multiplier of the first element of the input generator.

def seive():
    g = filter(int2())
    while True:
        yield g.next()
        g = filter(g)

prime = seive()

Here prime is a generator that conceptually contains all prime numbers! Let us take first 10 from it:

for x in xrange(0, 10): print prime.next()
Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s