# Test pierwszości Millera-Rabina 
import random 

# Funkcja pomocnicza do obliczania potęgi modulo
# Zwraca (x^y) % p 
def power(x, y, p): 
    
    # Inicjalizacja
    res = 1 
    
    # Aktualizacja wartości x, gdy x większe lub równe p
    x = x % p 
    while (y > 0): 
        
        # Jeżeli y jest nieparzyste, mnożę x przez wartość res 
        if (y & 1): 
            res = (res * x) % p 

        # Teraz y musi już być parzyste
        y = y>>1 # y = y/2 
        x = (x * x) % p 
    
    return res 

# Ta funkcja jest wywoływana we wszystkich k próbach. Funkcja zwraca 
# False, jeżeli n jest liczbą złożoną, i True jeżeli n jest 
# liczbą prawdopodobnie pierwszą. d to taka  
# liczba nieparzysta, że dla pewnego r>=1 d*2^r = n-1

def miillerTest(d, n): 
    
    # Losowanie wartość z przedziału [2..n-2] 
    # Przypadek brzegowy, należy sprawdzić, czy n > 4 
    a = 2 + random.randint(1, n - 4) 

    # Obliczam a^d % n 
    x = power(a, d, n) 

    if (x == 1 or x == n - 1): 
        return True 

    # Podnoszę x do kwadratu, dopóki:
    # (i) d jest różne od n-1 
    # (ii) (x^2) % n jest różne od 1 
    # (iii) (x^2) % n jest różne od n-1
     
    while (d != n - 1): 
        x = (x * x) % n 
        d *= 2 

        if (x == 1): 
            return False 
        if (x == n - 1): 
            return True 

    # Liczba jest złożona
    return False 

# Funkcja zwraca False, jeżeli n jest liczbą złożoną, i True jeżeli n 
# jest prawdopodobnie pierwsza. k to parametr wejściowy określający  
# dokładność testu. Im większa wartość k, tym test jest bardziej dokładny
def isPrime( n, k): 
    
    # Przypadki brzegowe
    if (n <= 1 or n == 4): 
        return False 
    if (n <= 3): 
        return True 

    # Znajduję takie r, że dla pewnego r >= 1 
    # n = 2^d * r + 1
    d = n - 1 
    while (d % 2 == 0): 
        d //= 2 

    # Powtarzam procedurę k razy 
    for i in range(k): 
        if (miillerTest(d, n) == False): 
            return False 

    return True 

# Główny program
# Liczba iteracji
k = 4 

print("Wszystkie liczby pierwsze mniejsze niż 1000: ")
print()
for n in range(1,1000): 
    if (isPrime(n, k)): 
        print(n , end=" ")

# Wyświetlam 3 puste linie
print('\n' * 3)