Iteráció osztók felett

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. július 10-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

Az osztók keresése (próbaosztás ) egy algoritmus egy szám egyszerűségének faktorálására vagy tesztelésére az összes lehetséges osztó kimerítő felsorolásával .

Az algoritmus leírása

Az osztók felsorolása általában az összes egész szám (opcióként: prím ) számozásából áll, 2-től az n faktorizálható szám négyzetgyökéig , és kiszámítjuk az n -t e számok mindegyikével osztva . Ha valamely i számmal való osztás maradéka 0, akkor i osztója n -nek . Ebben az esetben vagy n -t kompozitnak nyilvánítunk, és az algoritmus befejeződik (ha n-t prímként teszteljük ) , vagy n -t csökkentjük i -vel, és az eljárás megismétlődik (ha n faktorizálva van ). Amikor elérjük n négyzetgyökét, és lehetetlenné válik n-t bármely kisebb számra redukálni , n- t prímnek nyilvánítjuk [1] .

A felsorolás felgyorsítása érdekében gyakran még az osztókat sem ellenőrzik, kivéve a 2-es számot, valamint azokat az osztókat, amelyek a három többszörösei, kivéve a 3-at. Ebben az esetben a tesztet háromszor gyorsítják, mivel mindenből hat egymást követő potenciálosztónál csak kettőt kell ellenőrizni, mégpedig a 6 k ±1 alakból, ahol k  természetes szám .

Sebesség

A legrosszabb eset az, ha 2-től n gyökeréig kell iterálni . Ennek az algoritmusnak a bonyolultsága

Példa

Szemléltetésképpen soroljuk fel az n = 29 szám osztóit. i az n  lehetséges osztói .

én n % i
2 egy
3 2
négy egy
5 négy

Mivel a 29 maradékai közül egyik sem 0, a 29-et prímnek nyilvánítják.

Legyen most n = 7399, akkor [2]

én n % i
2 egy
3 egy
négy 3
5 négy
6 egy
7 0

Mivel a 7399 7-tel való osztásának maradéka 0, ezért 7399 nem prím.

Gyakorlati alkalmazás

Gyakorlati feladatokban ezt az algoritmust nagy számítási bonyolultsága miatt ritkán alkalmazzák , azonban alkalmazása indokolt, ha az ellenőrzött számok viszonylag kicsik, mivel ez az algoritmus meglehetősen könnyen megvalósítható [1] .

Lásd még

Jegyzetek

  1. ↑ 12 gyermek , 2009 , pp. 117-118.
  2. ↑ Crandall, Pomerance, 2005 , pp. 117-119.

Irodalom

Linkek