Iteration over divisorer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. juli 2018; checks kræver 5 redigeringer .

Søgning efter divisorer ( forsøgsdeling ) er en algoritme til faktorisering eller test af enkeltheden af et tal ved udtømmende at opregne alle mulige potentielle divisorer .

Beskrivelse af algoritmen

Normalt består opregning af divisorer i opregning af alle heltal (som en mulighed: primtal ) fra 2 til kvadratroden af det faktoriserbare tal n og i at beregne resten af at dividere n med hvert af disse tal. Hvis resten af division med et tal i er 0, så er i en divisor af n . I dette tilfælde er enten n erklæret sammensat, og algoritmen afsluttes (hvis n testes som prime ) , eller n reduceres med i , og proceduren gentages (hvis n er faktoriseret ). Når kvadratroden af n er nået og umuligheden af at reducere n til et af de mindre tal, er n erklæret som primtal [1] .

For at fremskynde optællingen kontrolleres ofte ikke lige divisorer, bortset fra tallet 2, samt divisorer, der er multipla af tre, bortset fra tallet 3. I dette tilfælde accelereres testen tre gange, da ud af hver seks på hinanden følgende potentielle divisorer er det nødvendigt at kontrollere kun to, nemlig af formen 6 k ±1, hvor k er et naturligt tal .

Hastighed

Det værste tilfælde er, hvis du skal iterere fra 2 til roden af n . Kompleksiteten af denne algoritme

O(n^{{1/2}})

Eksempel

For at illustrere det, lad os opregne divisorerne for tallet n = 29. i er de mulige divisorer af n .

$[n^{{1/2}}]=5$

jeg	n % i
2	en
3	2
fire	en
5	fire

Da ingen af resten af 29 er 0, er 29 erklæret prime.

Lad nu n = 7399, derefter [2]

$[n^{{1/2}}]=86$

jeg	n % i
2	en
3	en
fire	3
5	fire
6	en
7	0

Da resten af divisionen af 7399 med 7 er 0, så er 7399 ikke primtal.

Praktisk anvendelse

I praktiske problemer bruges denne algoritme sjældent på grund af dens høje beregningsmæssige kompleksitet , men dens brug er berettiget, hvis tallene, der kontrolleres, er relativt små, da denne algoritme er ret nem at implementere [1] .

Se også

Noter

↑ 12 Childs , 2009 , s. 117-118.
↑ Crandall, Pomerance, 2005 , s. 117-119.

Litteratur

Lindsay N.Childs. En konkret introduktion til højere algebra. — 3. udg. — New York, 2009. — 603 s.
Richard Crandall, Carl Pomerance. Primtal. Et beregningsmæssigt perspektiv . — 2. udg. - New York, 2005. - 597 s.