Algoritmi pri praštevilih

Za praštevila obstaja mnogo algoritmov. To ti pa nič ne pomaga če sploh ne veš kaj praštevila so.

Eratostenovo rešeto

Iskanje praštevil je pomembno tudi v sodobnem času, zlasti na področju kriptografije, kjer se uporabljajo za zaščito podatkov. Klasična metoda za iskanje praštevil je Eratostenovo rešeto, starodaven algoritem, ki postopno odstranjuje večkratnike manjših praštevil in tako razkrije vsa praštevila do dane meje. Danes se uporabljajo veliko hitrejši algoritmi, kot so Miller-Rabinov test in AKS-algoritem, s katerimi lahko preverjamo praštevilskost tudi izjemno velikih števil.

Eratostenovo rešeto najprej ustvari tabelo, v kateri predpostavimo, da so vsa števila od 2 do n praštevila. Nato zaporedoma jemljemo naslednje še neizločeno število p (ki je s tem praštevilo) in odstranimo vse njegove večkratnike, pri čemer začnemo pri p², ker so večkratniki manjši od p² že izločeni z manjšimi praštevili. Postopek končamo, ko presežemo √n, saj ima vsako sestavljeno število vsaj en prafaktor ≤ √n. Časovna poraba korakov je približno sorazmerna z n · log log n (vsako sestavljeno število “zadene” njegov najmanjši prafaktor), poraba pomnilnika pa je približno sorazmerna z n, če hranimo eno logično vrednost na število

Primer implementacije:

def eratostenovo_reseto(n):
    # vrne seznam praštevil ≤ n
    if n < 2:
        return []

    je_prastevilo = [True] * (n + 1)
    je_prastevilo[0] = je_prastevilo[1] = False

    p = 2
    while p * p <= n:
        if je_prastevilo[p]:
            # začnemo pri p*p, ker so manjši večkratniki že obdelani
            for m in range(p * p, n + 1, p):
                je_prastevilo[m] = False
        p += 1

    return [i for i, v in enumerate(je_prastevilo) if v]

Razcep na praštevila

Zelo uporaben algoritem je tudi algoritem za razcep števila na praštevila, ki ga sestavljajo. Temelji na iskanju najmanjših praštevil, ki delijo dano število. Začnemo pri 2 in preverjamo, ali deli število n. Če da, ga delimo toliko časa, dokler je deljivo, in zabeležimo praštevilo ter število delitev kot njegov eksponent. Nato nadaljujemo z naslednjimi možnimi delitelji (pri čemer lahko po 2 preverjamo le liha števila). Postopek se konča, ko je preostanek števila manjši ali enak 1. V najslabšem primeru moramo preveriti vse delitelje do kvadratnega korena števila, saj če n nima nobenega manjšega delitelja, je sam praštevilo. Za manjša števila je ta pristop zelo učinkovit, pri večjih pa se uporablja hitrejše metode, kot so razcep z naključnim iskanjem faktorjev (Pollardov ρ-algoritem) ali kvadratna sita, ki temeljijo na naprednejših idejah iz teorije števil in verjetnostnih postopkih.

Primer implementacije:

def razcep_na_prastevila(n):
    # vrne seznam (praštevil, eksponentov) za podano število n
    faktorji = []
    p = 2
    while p * p <= n:
        if n % p == 0:
            k = 0
            while n % p == 0:
                n //= p
                k += 1
            faktorji.append((p, k))
        p += 1 if p == 2 else 2  # po 2 preverjamo le liha števila
    if n > 1:
        faktorji.append((n, 1))
    return faktorji