Iterointi jakajien yli
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. heinäkuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .Jakajien haku ( kokeilujako ) on algoritmi luvun yksinkertaisuuden laskemiseen tai testaamiseen luettelemalla tyhjentävästi kaikki mahdolliset jakajat .
Algoritmin kuvaus
Yleensä jakajien laskeminen koostuu kaikkien kokonaislukujen (valinnaisena: alkuluku ) laskemisesta 2:sta kertoitettavan luvun n neliöjuureen ja n: n jaon jäännöksen laskemisesta kullakin näistä luvuista. Jos jakojäännös jollakin luvulla i on 0, niin i on luvun n jakaja . Tässä tapauksessa joko n julistetaan komposiitiksi ja algoritmi päättyy (jos n:ää testataan alkulukuna ) tai n :ää vähennetään i :llä ja toiminto toistetaan (jos n on kertoimella ). Kun n: n neliöjuuri saavutetaan ja n :ää ei ole mahdollista pelkistää pienemmäksi luvuksi, n julistetaan alkuluvuksi [1] .
Luettelon nopeuttamiseksi usein ei tarkisteta paria jakajia lukuun ottamatta lukua 2, samoin kuin jakajia, jotka ovat kolmen kerrannaisia lukuun ottamatta lukua 3. Tässä tapauksessa testiä kiihdytetään kolme kertaa, koska jokaisesta kuusi peräkkäistä potentiaalin jakajaa on tarpeen tarkistaa vain kaksi, nimittäin muotoa 6 k ±1, jossa k on luonnollinen luku .
Nopeus
Pahin tapaus on, jos sinun on iteroitava 2:sta n: n juureen . Tämän algoritmin monimutkaisuus
Esimerkki
Havainnollistaaksemme luetellaan luvun n = 29 jakajat. i ovat luvun n mahdollisia jakajia .
![[n^{{1/2}}]=5](https://wikimedia.org/api/rest_v1/media/math/render/svg/41f9043a9dbbd56e524b5521ad4868cc73b73800)
| i | n % i |
|---|---|
| 2 | yksi |
| 3 | 2 |
| neljä | yksi |
| 5 | neljä |
Koska mikään 29:n jäännöksistä ei ole 0, 29 julistetaan alkuluvuksi.
Olkoon nyt n = 7399, sitten [2]
![[n^{{1/2}}]=86](https://wikimedia.org/api/rest_v1/media/math/render/svg/05573d4c9152d5ece37459066e8c00cdf62035ec)
| i | n % i |
|---|---|
| 2 | yksi |
| 3 | yksi |
| neljä | 3 |
| 5 | neljä |
| 6 | yksi |
| 7 | 0 |
Koska 7399:n jaon jäännös 7:llä on 0, niin 7399 ei ole alkuluku.
Käytännön sovellus
Käytännön ongelmissa tätä algoritmia käytetään harvoin sen suuren laskennallisen monimutkaisuuden vuoksi, mutta sen käyttö on perusteltua, jos tarkastettavat luvut ovat suhteellisen pieniä, koska tämä algoritmi on melko helppo toteuttaa [1] .
Katso myös
Muistiinpanot
- ↑ 12 lasta , 2009 , s. 117-118.
- ↑ Crandall, Pomerance, 2005 , s. 117-119.
Kirjallisuus
- Lindsay N. Childs. Konkreettinen johdatus korkeampaan algebraan. – 3. painos - New York, 2009. - 603 s.
- Richard Crandall, Carl Pomerance. alkuluvut. Laskennallinen näkökulma . – 2. painos - New York, 2005. - 597 s.
Linkit
- Javascript Prime Factor Calculator käyttäen kokeilujakoa Arkistoitu 10. tammikuuta 2015 Wayback Machineen . Pystyy käsittelemään numeroita aina 9×10 15 asti
- Faktorisointi . wikia. Haettu 29. maaliskuuta 2022. Arkistoitu alkuperäisestä 28. joulukuuta 2018.