PRZYKŁADOWE ROZWIĄZANIE:

Poprawa złożoności algorytmu: 

W przedstawionym w podręczniku algorytmie nie ma potrzeby sprawdzania każdej liczby aż do n przy szukaniu wielokrotności. Wystarczy sprawdzać do pierwiastka kwadratowego z n, ponieważ jeśli liczba ma dzielnik większy niż jej pierwiastek kwadratowy, to drugi dzielnik musi być mniejszy, a zatem zostałby już znaleziony.

Ponadto algorytm rozpoczyna przesiewanie od 2, ale wszystkie wielokrotności liczby 2 poza nią samą nie mogą być liczbami pierwszymi. Następnie przechodzi do 3, 4 (które już zostało przesiane jako wielokrotność 2), 5 itd. Można to zoptymalizować, przeskakując wszystkie parzyste liczby poza 2.

Poniżej zaprezentowano ulepszony kod funkcji:

def generuj(n):
    sqrt_n = int(n**0.5) + 1
    T = [True] * (n+1)
    T[0] = T[1] = False  # 0 i 1 nie są liczbami pierwszymi
    
    for i in range(2, sqrt_n):
        if T[i]:  # Jeśli i jest liczbą pierwszą
            # Wykreślamy wszystkie wielokrotności i, zaczynając od i*i
            for m in range(i*i, n+1, i):
                T[m] = False
    
    # Wypisanie liczb pierwszych
    for i in range(2, n+1):
        if T[i]:
            print(i)

generuj(40)

Ulepszona wersja algorytmu sita Eratostenesa nadal ma złożoność obliczeniową $O(nlogn)$ (złożoność liniowo-logarytmiczną), ponieważ główna idea algorytmu pozostaje niezmieniona. Optymalizacje, które zastosowaliśmy, nie zmieniają fundamentalnej złożoności obliczeniowej algorytmu, ale poprawiają stałe czasy i efektywność, co jest zauważalne szczególnie przy dużych wartościach n.