main

  1"""Program na overenie, či je zadané číslo prvočíslom."""
  2
  3# Importujeme knižnicu random pre generovanie náhodných čísel,
  4# pretože ju budeme potrebovať pri heuristickej metóde Miller-Rabin Test.
  5
  6import random
  7
  8
  9def prvocislo(n: int) -> bool:
 10    """Funkcia 'prvocislo' na overenie, či je číslo prvočíslo.
 11
 12    Delenie od 2 do sqrt(n): Táto
 13    metóda zahŕňa delenie čísla n od 2 až do jeho druhej
 14    odmocniny. Ak sa nedá deliť žiadnym číslom v tomto rozsahu,
 15    potom sa považuje za prvočíslo.
 16
 17    :param n: Testované číslo.
 18    :return: Existencia prvočísla.
 19    """
 20    # Overenie či číslo je menšie alebo rovné 2
 21    if n <= 2:
 22        return n == 2
 23    # Overenie či číslo je párne
 24    elif n % 2 == 0:
 25        return False
 26    # Iterovanie od 3 po odmocninu z čísla + 1
 27    for i in range(3, int(n ** 0.5) + 1, 2):
 28        # Ak sa delí bez zvyšku, nie je to prvočíslo
 29        if n % i == 0:
 30            return False
 31    # Ak sa nenašlo žiadne deliteľné číslo, je to prvočíslo
 32    return True
 33
 34
 35def prvocislo_mr(n: int, k: int = 5) -> bool:
 36    """Funkcia 'prvocislo_mr' naoverenie či je číslo prvočíslo.
 37
 38    Miller-Rabin test funguje tak,
 39    že pre zadané číslo n, prvý krok je rozklad n-1 na d*2^r.
 40    Potom sa vyberie náhodné číslo a, ktoré sa zvolí z
 41    intervalu od 2 do n-2. Ďalej sa vykoná výpočet a^d mod n.
 42    Ak sa výsledok rovná 1 alebo n-1, číslo sa považuje za
 43    možné prvočíslo a test sa opakuje s iným číslom a.
 44    Ak sa výsledok nerovná ani 1 ani n-1, prechádza sa
 45    cez cyklus, kde sa výpočet opakuje s výsledkom
 46    predchádzajúceho výpočtu, kým sa neobjaví výsledok
 47    n-1 alebo kým sa nevykoná r-1 iterácií. Ak sa v cykle
 48    nedosiahne výsledok n-1, číslo sa považuje za zložené.
 49
 50    :param n: Testované číslo.
 51    :param k: Počet iterácií Miller-Rabin testu.
 52    :return: Existencia prvočísla.
 53    """
 54    # Ak je číslo párne alebo delitelné 3, vrátime False.
 55    if n % 2 == 0 or n % 3 == 0:
 56        return False
 57    # Inicializujeme premenné 'r' a 'd' pre kroky Miller-Rabin testu.
 58    r, d = 0, n - 1
 59    # rozklad n-1 na d*2^r
 60    while d % 2 == 0:
 61        r += 1
 62        d //= 2
 63    # Pomocou for cyklu vykonáme 'k' iterácií Miller-Rabin testu
 64    # s náhodnými číslami od 2 do n-2.
 65    for _ in range(k):
 66        a = random.randint(2, n - 2)
 67        # výpočet a^d mod n
 68        x = pow(a, d, n)
 69        """
 70            Ak sa výsledok nerovná ani 1 ani n-1, prechádza sa cez cyklus,
 71            kde sa výpočet opakuje s výsledkom predchádzajúceho výpočtu.
 72            kým sa neobjaví výsledok n-1 alebo kým sa nevykoná r-1 iterácií.
 73        """
 74        if x == 1 or x == n - 1:
 75            continue
 76        for _ in range(r - 1):
 77            x = pow(x, 2, n)
 78            """
 79                Ak sa v cykle nedosiahne výsledok n-1,
 80                číslo sa považuje za zložené.
 81            """
 82            if x == n - 1:
 83                break
 84        else:
 85            return False
 86    return True
 87
 88
 89if __name__ == '__main__':
 90    while True:
 91        """
 92        Vstup čísla od používateľa a jeho ošetrienie aby bolo
 93        číslo zadané užívateľom kladné celé číslo.
 94        """
 95        try:
 96            cislo = int(input("Zadaj cislo: "))
 97            # Podmienka na overenie kladnosti čísla.
 98            if cislo <= 0:
 99                print("Zadaj kladne celo cislo.")
100                continue
101            break
102        # Výpis chybovej hlášky ak sa zadal vstup iný ako typ int
103        except ValueError:
104            print("Zadaj validne cele cislo.")
105
106    # Volanie funkcií
107    """
108        Ak je číslo väčšie ako 1000 zavolá funkciu 'prvocislo_mr', čiže
109        heuristickú metódu Miller-Rabin test.
110    """
111    if cislo > 1000:
112        if prvocislo_mr(cislo):
113            print(f"{cislo} je prvocislo."
114                  f" Pouzita heuristicka metoda: Miller-Rabin test.")
115        else:
116            print(f"{cislo} nie je prvocislo. "
117                  f"Pouzita heuristicka metoda: Miller-Rabin test.")
118        """
119            Ak je číslo menšie alebo rovno 1000 zavolá funkciu 'prvocislo',
120            čiže metódu delenia od 2 do sqrt(n)
121        """
122    else:
123        if prvocislo(cislo):
124            print(f"{cislo} je prvocislo. Pouzita deterministicka metoda.")
125        else:
126            print(f"{cislo} nie je prvocislo. Pouzita deterministicka metoda.")