ispitivanje slozenosti prirodnog broja

Kao sto sam i rekao zanimaju me neki najbrzi algoritmi(ili kodovi u C++) koji ispituju slozenost proizvoljnog prirodnog broja.

Pa, jednostavno ako je broj n deljiv sa nekim brojem u intervalu [2,round(sqrt(n))] onda je složen, a u suprotnom prost.

Potpis

If you don't live for something, you will die for nothing.

To se cak moze poboljsati tako sto se medju deliocima tog broja ne proveravaju svi prirodni brojevi u intervalu nego samo prosti, sto zahteva neku rekurziju. Ali mene zanima nesto brze, kao sto sam i rekao.

Uvijek mozes precomputati tablicu prostih brojeva do nekih granica i uz pomoc nje provjeravati.
Ovo je ujedno i najbrze rijesenje.

A zasto ne postoji brze resenje?

http://en.wikipedia.org/wiki/Integer_factorization
nalazi se dosta linkova na razlicite algoritme, vrijedi pogledati.

http://en.wikipedia.org/wiki/Primality_test
mozda je ovo vise ono sto tebi treba,
pogledaj tamo recenicu i link sto pise o radu: "Manindra Agrawal, Nitin Saxena and Neeraj Kayal"

_{[Ovu poruku je menjao emiraga dana 03.05.2006. u 18:16 GMT+1]}

logicki nemoguce

koliku brzinu ti zelis???

Zato jer, da si pročitao članak na wikipediji, vidio bi da je faktorizacija integera jedan od onih bolesnijih problema za koje se ni ne zna da li su u P ili NP klasi (sl. npr problemu provjere da li su dva grafa izomorfna - brutforsanje svih bijekcija među skupovima vrhova jest jedini potpuno točan način).

Sve što možeš jest pronaći neki gotovi algo koji su smislili puno veći mozgovi od tebe a koji reducira prostor pretraživanja što je moguće više i nadati se da je dovoljno brz za tvoje potrebe. Gore su ti linkovi, počni kopati ;)

Potpis

Put the funk in funktion.

Najbrze ti je da ispitujes da li je deljiv prostim brojevima od 2 do koren iz n, a proste brojeve nadji preko eratostenovog sita.

Potpis

Math is like love. A simple idea but it can get complicated.

ja hocu najmanju mogucu, ako postoji, ili dokaz da ona ne postoji. Kao sto je i rekao cynique to je jos otvoren problem.



Ma mene su i zanimali gotovi algoritmi koje sam i dobio. Zato vam se puno zahvaljujem.




Opet isto ako kazes da je nesto najbrze onda postoji i dokaz za to. Jeste da to logicki izgleda ok, ali sta mislis da se nadje relativno jednostavna formula koja generise proste brojeva, sa kojom bi to islo brze.

Ako imas tabelu prostih brojeva od [0, 100] onda mozes u kratkom vremenu provjeriti dali je tvoj broj koji je iz [0, sqr(100)] slozen ili ne.
A tabelu ces samo jednom generirati i imati precomputanu na koristenje tvom programu.

I ako postoji takva neka funkcija, ako vec ne postoji, tesko da cemo je mi izvesti i dokazati...

Razumem ja sa ti hoces da pitas ali sta ce to tebi. Da imas dokaz sigurno, kao sto imas i dokaz da sort ne moze przeod NlogN ali to da bi razumeo treba ti dosta teorije...

Potpis

Math is like love. A simple idea but it can get complicated.

Takav mi je odgovor trebao. Znaci do sad je najbrzi ovaj sa eratostenovim sitom, jel da?

Nije. Ja sam skontao jednu foru da se dosta ubrza stvar.

Radi se o tome da se sa jednim deljenjem moze eliminisati veliki postotak brojeva. Recimo da je broj koji izucavamo X. Imamo jednu konstantu, koju cemo nazvati Y. :-) Y mozes sam definisati, sto je veci, veca je efikasnost, ali se takodje i povecava lookup-tabela koju ces koristiti. Y se racuna na sledeci nacin:

Y = 2 * 3 * 5 * 7 ....

Dakle mnozimo proste brojeve.

E sad. Ukoliko X podelimo sa Y, i ostatak je 0 ili deljiv sa nekim od sastavnih brojeva Y (brojeva koje smo pomnozili), broj koji izucavamo nije prost broj, posto je i on deljiv sa istim sastavnim brojem.

Mozda nisam bas jasan, pa evo mali primer:

Y = 2 * 3 = 6

N = X mod Y = X mod 6

ako je N = 0, 2, 3 ili 4, onda broj nije prost. Dakle jednim deljenjem smo eliminisali 66.67% brojeva.

Sledeci slucaj:

Y = 2 * 3 * 5 = 30

N = X mod Y

ako je N = 0, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27 ili 28, onda X nije prost broj.
U ovom slucaju smo eliminisali 73.33% brojeva sa jednim deljenjem.

Vrednosti koje oznacavaju slozene brojeve mozemo pamtiti kao bit array, dakle table ce zauzeti Y / 8 bajtova.

Na primer ako uzmemo proste vrednosti do 23, Y ce biti 223092870, dakle velicina tabele je nesto vise od 26 megabajta. Naravno ovo nece puno znaciti ako je broj zaista prost, ali ce pomoci za eliminaciju slozenih brojeva. A mogu se koristiti i dva (ili vise) deljenja, da bi se ustedelo na memoriji, u tom slucaju bi bilo:

Y1 = 2 * 5 * 11 * ...
Y2 = 3 * 7 * 13 * ...

moze i da se proverava da li je . Ako jeste onda je prost, u suprotnom je slozen. Mada ne znam koliko je ovo efikasno za velike .



_{[Ovu poruku je menjao qzqzqz dana 05.05.2006. u 14:57 GMT+1]}

Informaciju da li je neki broj prost ili nije (bez faktorisanja)
moguce je dobiti u polinomijalnom vremenu
http://en.wikipedia.org/wiki/AKS_primality_test

(nadam se da se ne ljutite na mene sto samo lijepim samo linkove od wikipedije)

Evo i nekih implementacija [nije wikipedia]
http://fatphil.org/maths/AKS/#Implementations

Da (izvinjavam se zbog predjasnjeg odgovora - nisam procitao da tebe bas zanima najbrzi algoritam). Da postoje neki algoritmi koji imaju plimijalnu slozenost ali se vecina njih zasniva na verovatnoci. O toe mozes da njadje dosta u neki knjigama o RSA i tome slicno. A evo i ja sam zaheftao jedan mali pdf....

Potpis

Math is like love. A simple idea but it can get complicated.