Iterace přes dělitele
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. července 2018; kontroly vyžadují 5 úprav .Hledání dělitelů ( zkušební dělení ) je algoritmus pro faktoring nebo testování jednoduchosti čísla vyčerpávajícím výčtem všech možných potenciálních dělitelů .
Popis algoritmu
Výčet dělitelů obvykle spočívá ve výčtu všech celočíselných (jako možnost: prvočíslo ) čísel od 2 do druhé odmocniny faktorizovatelného čísla n a ve výpočtu zbytku dělení n každým z těchto čísel. Jestliže zbytek dělení nějakým číslem i je 0, pak i je dělitel n . V tomto případě je buď n deklarováno jako složené a algoritmus končí (pokud je n testováno jako prvočíslo ) , nebo je n redukováno o i a postup se opakuje (pokud je n faktorizováno ). Po dosažení druhé odmocniny n a nemožnosti redukovat n na žádné z menších čísel je n prohlášeno za prvočíslo [1] .
Pro urychlení výčtu se často nekontrolují ani dělitelé, kromě čísla 2, stejně jako dělitelé, kteří jsou násobky tří, kromě čísla 3. V tomto případě je test urychlen třikrát, protože z každého šest po sobě jdoucích potenciálních dělitelů je třeba zkontrolovat pouze dva, a to ve tvaru 6 k ±1, kde k je přirozené číslo .
Rychlost
Nejhorší případ je, když musíte iterovat od 2 do kořene n . Složitost tohoto algoritmu
Příklad
Pro ilustraci vyjmenujme dělitele čísla n = 29. i jsou možné dělitele n .
![[n^{{1/2}}]=5](https://wikimedia.org/api/rest_v1/media/math/render/svg/41f9043a9dbbd56e524b5521ad4868cc73b73800)
| i | n % i |
|---|---|
| 2 | jeden |
| 3 | 2 |
| čtyři | jeden |
| 5 | čtyři |
Protože žádný ze zbytků 29 není 0, je 29 prohlášeno za prvočíslo.
Nechť nyní n = 7399, pak [2]
![[n^{{1/2}}]=86](https://wikimedia.org/api/rest_v1/media/math/render/svg/05573d4c9152d5ece37459066e8c00cdf62035ec)
| i | n % i |
|---|---|
| 2 | jeden |
| 3 | jeden |
| čtyři | 3 |
| 5 | čtyři |
| 6 | jeden |
| 7 | 0 |
Protože zbytek dělení 7399 7 je 0, pak 7399 není prvočíslo.
Praktická aplikace
V praktických problémech se tento algoritmus používá jen zřídka kvůli své vysoké výpočetní náročnosti , jeho použití je však oprávněné, pokud jsou kontrolovaná čísla relativně malá, protože tento algoritmus je poměrně snadno implementovatelný [1] .
Viz také
Poznámky
- ↑ 12 Childs , 2009 , s. 117-118.
- ↑ Crandall, Pomerance, 2005 , pp. 117-119.
Literatura
- Lindsay N.Childs. Konkrétní úvod do vyšší algebry. — 3. vyd. — New York, 2009. — 603 s.
- Richard Crandall, Carl Pomerance. prvočísla. Výpočetní perspektiva . — 2. vyd. - New York, 2005. - 597 s.
Odkazy
- Javascript Prime Factor Calculator pomocí zkušební divize Archivováno 10. ledna 2015 na Wayback Machine . Schopný zpracovávat čísla až 9× 1015
- Faktorizace . wikia. Získáno 29. března 2022. Archivováno z originálu dne 28. prosince 2018.