суббота, 20 февраля 2016 г.

Imperative Eratosthenes sieve

Algorithm is very-very simple and is learning at the school :)

def erato(m):
    # list of all numbers to m: 1 - free cell, 0 - aliquot to prime
    lst = [1 for i in range(m)]
    n = 2 # starts from 2
    while n < m: # take next prime
        for i in range(n, m): # looking for free cell
            if lst[i]: break # 1 - free, i.e. not aliquot to others
        if i == m-1: return # no more free, stop
        n = i # keep found free
        yield n # and it's prime!
        j = 2 # multiplier: 2, 3, 4, 5...
        while i < m: # checks aliquot to found prime n
            lst[i] = 0
            i = n*j # checks 2n, 3n, 4n, 5n, 6n, ...
            j += 1 # multipliers: 2, 3, 4, 5...

print list(erato(300))

Комментариев нет:

Отправить комментарий

Thanks for your posting!