Razcep na prafaktorje

Naloga

Kot ste se učili v osnovni šoli, lahko vsako število razcepimo v produkt praštevil. Tako je 252=2² 3²7¹ in 1944=2³3⁵.

Za domačo nalogo boste sprogramirali (zelo preprost in neučinkovit, a vsekakor poučen) postopek za razcep števil na prafaktorje. Napisali boste funkcijo, ki kot argument prejme število in kot rezultat vrne seznam terk, ki predstavljajo osnovo in potenco. Za gornja primera mora izgledati takole:

>>> razcep(252) [(2, 2), (3, 2), (7, 1)] >>> razcep(1944) [(2, 3), (3, 5)]

Naloge se lotite tako, da sprogramirate naslednje funkcije.

1. Napišite funkcijo, ki ugotovi, ali je dano število praštevilo (namig: glejte zapiske predavanj, vendar priporočam, da funkcijo prastevilo(n ) - četudi popolnoma enako moji - napišete ponovno sami). >>> prastevilo(42) False >>> prastevilo(43) True
2. Napišite funkcijo prastevila(n ), ki vrne vsa praštevila med (vključno!) 2 in n. >>> prastevila(100) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] >>> prastevila(43) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]</code> Funkcija naj deluje tako, da za vsa števila od 2 do n pokliče prvo funkcijo in če le-ta pravi, da gre za praštevilo, doda praštevilo na seznam.</li> <li>Napišite funkcijo <code>deljivost(n, i)</code>, ki pove, kolikokrat je n deljivo z i. <xmp class="brush: python">>>> deljivost(1944, 2) 3 >>> deljivost(1944, 3) 5 Namig: dokler je n deljivo z i, ga deli z i in štej, kolikokrat si ga delil.
3. Napišite funkcijo razcep(n ), ki naredi, kar zahteva naloga, pri čemer kliče funkciji prastevila in deljivost: za vsa praštevila med 2 in n ugotovi, kolikokrat delijo podano število in če ga delijo vsaj enkrat (torej, ne delijo), to doda v seznam. (Namig: če želiš dodati v seznam t terko (1, 2), rečeš t.append((1, 2)).)

Naloga za študente, ki so podvrženi dolgočasenju: Poleg gornjega sprogramiraj še boljšo, to je, hitrejšo funkcijo. Za test preveri, koliko časa potrebuje, da razcepi število 95256.

Rešitev

def prastevilo(n): for i in range(2, n): if n % i == 0: return False return True def prastevila(n): s = [] for i in range(2, n+1): if prastevilo(i): s.append(i) return s def deljivost(n, i): k = 0 while n % i == 0: k += 1 n //= i return k def razcep(n): t = [] for p in prastevila(n): d = deljivost(n, p) if d != 0: t.append((p, d)) return t

O prvi funkciji ni kaj povedati: že videno.

Druga kliče prvo in v seznam zlaga vsa števila, za katera le-ta vrne True. Paziti moramo le na meje: da dobimo vsa števila od 2 do n, kot zahteva naloga, uporabimo range(2, n++1).

Edina """težka""" funkcija je tretja. Dokler je n deljiv z i, ga delimo z i; mimogrede pa štejemo, kolikokrat smo to storili. Tako kot bi, recimo n += i k n-ju prištel i, bi ga n /= i delil z i, operator, ki smo ga uporabili, n //= i, pa ga celoštevilsko deli z i. (Hm, morda pa tudi ni tako težka. :))

Četrta pa zahteva le, da znamo klicati (lastne) funkcije: za vsa praštevila do n ugotovimo, kolikokrat delijo n in če ga, v seznam dodamo terko s praštevilom in potenco.

Pa še v eni vrstici

(Tole je seveda spet smo za tiste, ki jih ta šport zanima.)

Drugo in četrto funkcijo bi pri programiranju običajno v resnici napisali v eni vrstici, takšni, kot jo vidite spodaj. Prve ne, ker je neučinkovita, še počasnejša od rešitve zgoraj. Tretja pa je grda; najbrž se jo da v eni vrstici rešiti še na veliko drugih načinov, vendar so verjetno vsi grdi.

def prastevilo(n): return all(n % i for i in range(2, n)) def prastevila(n): return [i for i in range(2, n+1) if prastevilo(i)] def deljivost(n, i): return reduce(lambda xk, y: (xk[0] if xk[0]%i else xk[0]//i, xk[1] + (xk[0]%i==0)), range(n), (n, 0))[1] def razcep(n): return [(p, deljivost(n, p)) for p in prastevila(n) if n%p==0]