Alkutekijähajotelmalaskuri

Luvun Jakaminen Sen Alkulukurakennuspalikoihin

Jokainen yli 1:n kokonaisluku voidaan jakaa ainutlaatuiseksi joukoksi alkulukuja, jotka kerrottuina yhteen — sen alkutekijähajotelma. Syötä kokonaisluku, ja tämä laskuri löytää tuon hajotelman välittömästi, sekä sen, onko luku itse alkuluku.

Kaava

Aritmetiikan peruslause takaa, että jokaisella yli 1:n kokonaisluvulla N on täsmälleen yksi alkutekijähajotelma, tekijöiden kirjoitusjärjestykseen asti:

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

jossa jokainen $\vB{p_i}$ on eri alkuluku ja jokainen $\vC{a_i}$ kertoo, kuinka monta kertaa tuo alkuluku jakaa N:n tasaisesti.

Tämä laskuri löytää tuon hajotelman koejaon avulla: alkaen 2:sta, se tarkistaa toistuvasti, jakaako jokainen luku jäljellä olevan tasaisesti, jakaen sen pois (ja laskien kuinka monta kertaa) aina kun se onnistuu, ja siirtyen sitten seuraavaan ehdokkaaseen. Kun ehdokkaan neliö ylittää jäljellä olevan, mikä tahansa vielä jäljellä oleva on itsessään oltava alkuluku — mikä tahansa pienempi tekijä olisi jo löydetty:

$$\text{jos } \vD{d}^2 > \vE{\text{jäljellä oleva arvo}}, \text{ niin } \vE{\text{jäljellä oleva arvo}} \text{ on alkuluku}$$

Laskuesimerkki

Löydetään luvun 360 alkutekijähajotelma:

1. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 jakaa 3 kertaa; 45 on pariton, joten jatketaan).
2. 45 ÷ 3 = 15, ÷ 3 = 5 (3 jakaa 2 kertaa; 5 ei jaa enää 3:lla).
3. 5 jää jäljelle, eikä minkään seuraavan jakajan neliö ole ≤ 5, joten 5 itse on alkuluku.
4. Tulos: 2³ × 3² × 5.

Keskeiset Huomioitavat Tekijät

• Jokainen alkutekijähajotelma on ainutlaatuinen — tämän juuri aritmetiikan peruslause takaa. Riippumatta siitä, miten luku hajotetaan, sen alkutekijähajotelma tulee aina samaksi (tekijöiden kirjoitusjärjestystä lukuun ottamatta), minkä vuoksi alkutekijähajotelma on niin perustavanlaatuinen rakennuspalikka koko lukuteoriassa.
• Alkutekijähajotelma on mekanismi suurimman yhteisen tekijän tai pienimmän yhteisen jaettavan löytämiseen käsin. Kahden luvun alkutekijähajotelmien suora vertailu paljastaa suoraan niiden SYT:n (jaetut alkutekijät alemmalla jaetulla eksponentilla) ja PYJ:n (jokainen alkutekijä korkeammalla eksponentilla) — katso SYT/PYJ-laskuri tätä nimenomaista vertailua varten.
• Suurten lukujen tekijöihinjako muuttuu laskennallisesti paljon vaikeammaksi numeroiden määrän kasvaessa, mikä on joidenkin salausmenetelmien perusta. Koejako (tässä käytetty menetelmä) toimii hyvin luvuille, joita ihmiset tyypillisesti syöttävät käsin, mutta hyvin suuren, satoja numeroita sisältävän luvun tekijöihinjako voi olla laskennallisesti mahdotonta jopa tehokkaille tietokoneille — tämä vaikeus on juuri se, mikä on RSA-salauksen turvallisuuden taustalla.
• Alkuluvulla on täsmälleen yksi alkutekijä: se itse, ensimmäisessä potenssissa. Tästä syystä tämän laskurin “onko tämä luku alkuluku” -tarkistus tulee suoraan hajotelmaprosessista — jos koejako ei koskaan löydä lukua pienempää tekijää kuin luvun oma neliöjuuri, luvulla ei ole muuta hajotelmaa kuin se itse.

Yleiset Virheet

• Alkutekijähajotelman sekoittaminen täydelliseen tekijälistaan. Luvun 12 tekijät ovat 1, 2, 3, 4, 6 ja 12, mutta sen alkutekijähajotelma on vain 2² × 3 — alkutekijähajotelma säilyttää vain alkulukurakennuspalikat, ei jokaista lukua, joka jakaa tasaisesti.
• Luvun 1 kohteleminen alkulukuna. Määritelmän mukaan alkuluvulla on täsmälleen kaksi eri tekijää (1 ja se itse) — luvulla 1 on vain yksi, joten se ei ole alkuluku eikä yhdistetty luku, eikä se koskaan esiinny alkutekijähajotelmassa.
• Toistuvien alkutekijöiden unohtaminen. Luvun 8 alkutekijähajotelma on 2³, ei pelkästään “2” — unohtamalla kuinka monta kertaa alkuluku jakaa, muuttuu luku, jota hajotelma todella edustaa.

Hyödyllistä Tietoa

• Tarvitsetko kahden luvun suurimman yhteisen tekijän tai pienimmän yhteisen jaettavan yhden luvun omien tekijöiden sijaan? Suurin Yhteinen Tekijä Ja Pienin Yhteinen Jaettava -Laskuri vertailee suoraan kahden luvun alkutekijähajotelmia.
• Yksinkertaistatko murtolukua sen alimpaan muotoon? Murtolukulaskuri käyttää samoja jaettuja alkutekijöitä, jotka tämä laskuri löytää.
• Työskenteletkö sen sijaan erittäin suuren tai erittäin pienen luvun kanssa? Tieteellisen Merkintätavan Laskuri muuntaa standardimuodon ja tieteellisen muodon välillä.