Imperative Eratosthenes sieve
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))