Prvočíselný Rozklad

Rozklad Čísla na Jeho Prvočíselné Stavební Kameny

Každé celé číslo větší než 1 lze rozložit na jedinečnou množinu prvočísel násobených dohromady — jeho prvočíselný rozklad. Zadejte celé číslo, a tato kalkulačka okamžitě najde tento rozklad, spolu s tím, zda je samotné číslo prvočíslo.

Formule

Základní věta aritmetiky zaručuje, že každé celé číslo N větší než 1 má přesně jeden prvočíselný rozklad, až na pořadí, ve kterém jsou faktory zapsány:

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

kde každé $\vB{p_i}$ je odlišné prvočíslo a každé $\vC{a_i}$ je, kolikrát toto prvočíslo dělí N beze zbytku.

Tato kalkulačka najde tento rozklad pomocí zkusmého dělení: počínaje 2, opakovaně kontroluje, zda každé číslo dělí beze zbytku to, co zbývá, dělí jej (a počítá, kolikrát) kdykoli ano, pak přechází na dalšího kandidáta. Jakmile druhá mocnina kandidáta přesáhne to, co zbývá, cokoli stále zbývá musí být samo prvočíslo — jakýkoli menší faktor by už byl nalezen:

$$\text{pokud } \vD{d}^2 > \vE{\text{zbývající hodnota}}, \text{ pak } \vE{\text{zbývající hodnota}} \text{ je prvočíslo}$$

Řešený Příklad

Nalezení prvočíselného rozkladu 360:

1. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 dělí 3krát; 45 je liché, takže pokračujeme).
2. 45 ÷ 3 = 15, ÷ 3 = 5 (3 dělí 2krát; 5 už není dělitelné 3).
3. Zbývá 5, a žádný další dělitel jehož druhá mocnina je ≤ 5, takže 5 samotné je prvočíslo.
4. Výsledek: 2³ × 3² × 5.

Klíčové Faktory ke Zvážení

• Každý prvočíselný rozklad je jedinečný — to je přesně to, co zaručuje Základní věta aritmetiky. Bez ohledu na to, jak je číslo rozloženo, jeho prvočíselný rozklad vždy vyjde stejně (kromě pořadí, ve kterém jsou faktory zapsány), což je důvod, proč je prvočíselný rozklad tak základním stavebním kamenem napříč teorií čísel.
• Prvočíselný rozklad je mechanismus stojící za ručním hledáním Největšího Společného Dělitele nebo Nejmenšího Společného Násobku. Přímé porovnání prvočíselných rozkladů dvou čísel odhaluje jejich NSD (sdílené prvočíselné faktory, při nižším sdíleném exponentu) a NSN (každý prvočíselný faktor, při vyšším exponentu) — viz Kalkulačku NSD/NSN pro toto konkrétní porovnání.
• Faktorizace velkých čísel se s rostoucím počtem číslic výpočetně mnohem obtížnější, což je základem některých šifrovacích metod. Zkusmé dělení (metoda použitá zde) funguje dobře pro čísla, která lidé typicky zadávají ručně, ale faktorizace velmi velkého čísla se stovkami číslic může být výpočetně neproveditelná i pro výkonné počítače — tato obtížnost je přesně to, co stojí za bezpečností šifrování RSA.
• Prvočíslo má přesně jeden prvočíselný faktor: sebe sama, na první mocninu. To je důvod, proč kontrola „je toto číslo prvočíslo” této kalkulačky přímo vychází z procesu rozkladu — pokud zkusmé dělení nikdy nenajde faktor menší než vlastní druhá odmocnina čísla, číslo nemá žádný jiný rozklad než samo sebe.

Časté Chyby

• Zaměňování prvočíselného rozkladu s úplným seznamem faktorů. Faktory čísla 12 jsou 1, 2, 3, 4, 6 a 12, ale jeho prvočíselný rozklad je pouze 2² × 3 — prvočíselný rozklad zachovává pouze prvočíselné stavební kameny, ne každé číslo, které dělí beze zbytku.
• Zacházení s 1 jako s prvočíslem. Prvočíslo má z definice přesně dva odlišné dělitele (1 a sebe sama) — 1 má pouze jeden, takže není ani prvočíslo, ani složené číslo, a nikdy se neobjevuje v prvočíselném rozkladu.
• Ztráta přehledu o opakovaných prvočíselných faktorech. Prvočíselný rozklad čísla 8 je 2³, ne jen „2” — zapomenutí, kolikrát prvočíslo dělí beze zbytku, mění číslo, které rozklad skutečně reprezentuje.

Užitečné Informace

• Potřebujete Největšího Společného Dělitele nebo Nejmenší Společný Násobek dvou čísel místo vlastních faktorů jednoho čísla? Kalkulačka Největšího Společného Dělitele a Nejmenšího Společného Násobku přímo porovnává prvočíselné rozklady dvou čísel.
• Zjednodušujete zlomek na nejnižší tvar? Kalkulačka Zlomků používá stejné sdílené prvočíselné faktory, které najde tato kalkulačka.
• Pracujete místo toho s velmi velkým nebo velmi malým číslem? Kalkulačka Vědeckého Zápisu převádí mezi standardním a vědeckým zápisem.