Sito Eratostenesa

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

WPROWADZENIE

Algorytm szukania wszystkich liczb pierwszych nie większych od podanej liczby.

def sito(n):
    """Sito Eratostenesa - liczby pierwsze nie większe od n."""
    L = [0] + n * [1]
    p = 2
    q = p * p
    while q <= n:
        if L[p] == 1:  # liczba pierwsza
            i = q
            while i <= n:  # wyrzucam p*p, p*(p+1), p*(p+2),...
                L[i] = 0
                i = i + p
        p = p + 1
        q = p * p
    M = []
    for i in range(1, n+1):
        if L[i] == 1:
            M.append(i)
    return M

# Wersja bardzie zwarta.
def sito(n):                  # liczby pierwsze <= n
    """Sito Eratostenesa - liczby pierwsze nie większe od n."""
    L = [0] + n * [1]
    for p in range(2, n):     # wystarczy p do sqrt(n)
        q = p * p
        if q > n:
            break
        if L[p] == 1:         # liczba pierwsza
            # wyrzucam p*p, p*(p+1), p*(p+2),...
            for i in range(q, n+1, p):
                L[i] = 0
    return [i for i in range(1, n+1) if L[i]==1]