Itererar över divisorer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 juli 2018; kontroller kräver 5 redigeringar .

Sökning av divisorer ( försöksdivision ) är en algoritm för att faktorisera eller testa enkelheten hos ett tal genom att uttömmande räkna upp alla möjliga potentiella divisorer .

Beskrivning av algoritmen

Vanligtvis består uppräkning av divisorer i uppräkning av alla heltal (som ett alternativ: primtal ) från 2 till kvadratroten av det faktoriserbara talet n och i att beräkna resten av att dividera n med vart och ett av dessa tal. Om resten av division med något tal i är 0, så är i en divisor av n . I det här fallet deklareras antingen n sammansatt och algoritmen avslutas (om n testas som primtal ) , eller så reduceras n med i och proceduren upprepas (om n faktoriseras ). När kvadratroten av n nås och omöjligheten att reducera n till något av de mindre talen, deklareras n som primtal [1] .

För att påskynda uppräkningen kontrolleras ofta inte jämna divisorer, förutom talet 2, samt divisorer som är multiplar av tre, förutom talet 3. I det här fallet accelereras testet tre gånger, eftersom av varje sex på varandra följande potentialdelare är det nödvändigt att kontrollera endast två, nämligen av formen 6 k ±1, där k  är ett naturligt tal .

Hastighet

Det värsta fallet är om du måste iterera från 2 till roten av n . Komplexiteten i denna algoritm

Exempel

För att illustrera, låt oss räkna upp divisorerna för talet n = 29. i  är de möjliga divisorerna för n .

i n % i
2 ett
3 2
fyra ett
5 fyra

Eftersom ingen av resten av 29 är 0, deklareras 29 som primtal.

Låt nu n = 7399, sedan [2]

i n % i
2 ett
3 ett
fyra 3
5 fyra
6 ett
7 0

Eftersom resten av divisionen av 7399 med 7 är 0, är ​​7399 inte primtal.

Praktisk tillämpning

I praktiska problem används denna algoritm sällan på grund av dess höga beräkningskomplexitet , men dess användning är motiverad om siffrorna som kontrolleras är relativt små, eftersom denna algoritm är ganska lätt att implementera [1] .

Se även

Anteckningar

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

Litteratur

Länkar