Alkutekijähajotelma ja jakajat
Hajota N alkulukupotensseiksi ja laske jakajat
Alkutekijähajotelma ja jakajat on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Hajottakaa N tekijöihin
Jokainen ykköstä suurempi kokonaisluku on alkulukujen yksikäsitteinen tulo. Tämän hajotelman eli alkutekijähajotelman löytäminen avaa monia lukuteorian ongelmia. 🧩
Kokeilujaon idea
Ottakaa pienin n:n jakava alkuluku talteen, jakakaa se pois ja toistakaa. Tämä yksinkertainen kokeilujako pienentää n:n arvoon 1 asti.
Käykää neliöjuureen asti
Testatkaa jakajia i niin kauan kuin i*i on enintään n. Neliöjuuren jälkeen jäljellä voi olla korkeintaan yksi alkutekijä.
while i * i <= n:
...Erottakaa jokainen tekijä
Niin kauan kuin i jakaa n:n, jakakaa toistuvasti ja tallentakaa i. Näin saatte talteen kyseisen alkuluvun koko potenssin ennen seuraavaan siirtymistä.
while n % i == 0:
factors.append(i)
n //= iJäljelle jäävä alkuluku
Jos n on silmukan jälkeen edelleen suurempi kuin 1, se on itse neliöjuurta suurempi alkutekijä. Lisätkää se kerran.
if n > 1:
factors.append(n)Koko menetelmä
Yhdessä nämä vaiheet tuottavat tekijähajotelman ajassa O(sqrt n) ja palauttavat kaikki alkuluvut täysine kertalukuineen oikeassa järjestyksessä.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fRyhmitelkää potensseiksi
Jakajien laskemista varten tarvitsette jokaisen alkuluvun ja sen eksponentin, kuten 2^3 ettekä muotoa 2,2,2. Counter laskee toistot siististi.
from collections import Counter
exp = Counter(factorize(n))Jakajien lukumäärän kaava
Jos n on muotoa p1^a kertaa p2^b, jakajien lukumäärä on (a+1) kertaa (b+1). Jokainen eksponentti saa yhden lisävaihtoehdon.
Jakajien lukumäärä
Kertokaa jokaisen alkuluvun eksponenttiin yksi lisättynä kaikkien alkulukujen kesken. Näin saatte kaikkien jakajien lukumäärän ilman, että niitä tarvitsee luetella.
count = 1
for e in exp.values():
count *= (e + 1)Jakajien summa
Toinen kaava laskee jakajien summan kunkin alkuluvun geometrisen sarjan avulla. Sen tunteminen auttaa täydellisiin lukuihin ja aliquot-ongelmiin liittyvissä tehtävissä.
Nopeutta seulalla
Kun tekijöihinjakoja on paljon, esilaskekaa kunkin luvun pienin alkutekijä seulalla. Sen jälkeen jokainen kysely voidaan jakaa tekijöihin log n -vaiheessa.
Pikatarkistus
Soveltakaa jakajien lukumäärän kaavaa konkreettiseen lukuun.
Kertaus
Osaatte nyt jakaa luvun N tekijöihin kokeellisella jakamisella ajassa O(sqrt n), käsitellä jäljelle jäävän alkuluvun, ryhmitellä eksponentit ja laskea jakajien lukumäärän tulokaavalla. ✅
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Alkutekijähajotelma ja jakajat” ilmainen?
Kyllä – oppitunnin ”Alkutekijähajotelma ja jakajat” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Alkutekijähajotelma ja jakajat”?
Hajota N alkulukupotensseiksi ja laske jakajat Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Alkutekijähajotelma ja jakajat”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- GCD, LCM ja Eukleideen algoritmi
- Alkulukujen testaaminen sqrt(n):ään asti
- Eratostheneen seula
- Alkutekijähajotelma ja jakajat