from math import sqrt
from datetime import datetime

def generator_liczb_pierwszych(zakres):

    '''
    Funkcja generujaca liczby pierwsze poprzez sprawdzenie podzielnosci. Algorytm ulepszony
    w oparciu o: https://eduinf.waw.pl/inf/alg/001_search/0010.php
    :param zakres: Gorna granica zakresu w ktorym wyszukiwane beda liczby
    :return: Tuple: [0] - ilosc liczb pierwszych w przedziale,
                    [1] - lista liczb pierwszych z przedzialu
    '''

    lista_p = [2,3]
    liczba_p = len(lista_p)               # bo dwa i trzy jest pierwsze

    for i in range(5,zakres,2):

        flaga_d = False         #flaga informujaca o tym czy liczba jest pierwsza
        flaga_k = False         #flaga informujaca o tym czy liczba jest podzielna przez 6k+0,2,3
        k = i//6

        for j in range(1,k+1):
            if i%(j*6) == 0 or i%(j*6+2) == 0 or i%(j*6+3) == 0:
                flaga_k = True
                break
        if flaga_k: continue

        for czynnik in lista_p:

            if czynnik>int(sqrt(i)):
                break

            else:
                if i%czynnik == 0:
                    flaga_d = True

        if flaga_d == False:

            lista_p.append(i)
            liczba_p = len(lista_p)

    return liczba_p, lista_p

startTime = datetime.now()

liczby_pierwsze = generator_liczb_pierwszych(1000000)
print(liczby_pierwsze[0])

print(datetime.now() - startTime)