[es] - ispitivanje slozenosti prirodnog broja

stf
Stefan Mišković
Čačak

Član broj: 51276
Poruke: 65
*.152.eunet.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 14:05}

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

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

^{03.05.2006. u 14:05}

qzqzqz

Član broj: 66936
Poruke: 218
*.ptt.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 14:56}

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.

^{03.05.2006. u 14:56}

NrmMyth
Split, Kaštela

Član broj: 63456
Poruke: 839
*.cmu.carnet.hr.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 16:08}

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

http://www.last.fm/user/NrmMyth/

^{03.05.2006. u 16:08}

qzqzqz

Član broj: 66936
Poruke: 218
*.ptt.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 16:19}

A zasto ne postoji brze resenje?

^{03.05.2006. u 16:19}

emiraga

Član broj: 54285
Poruke: 32
217.199.142.*

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 17:11}

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]}

^{03.05.2006. u 17:11}

NrmMyth
Split, Kaštela

Član broj: 63456
Poruke: 839
*.cmu.carnet.hr.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{03.05.2006. u 18:30}

Citat:

qzqzqz: A zasto ne postoji brze resenje?

logicki nemoguce

koliku brzinu ti zelis???

http://www.last.fm/user/NrmMyth/

^{03.05.2006. u 18:30}

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
193.198.17.*

ICQ: 106979934
Sajt: istambuk.blogspot.com

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 02:15}

Citat:

qzqzqz: A zasto ne postoji brze resenje?

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 ;)

Put the funk in funktion.

^{04.05.2006. u 02:15}

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 185
212.200.12.*

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 02:37}

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

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

^{04.05.2006. u 02:37}

qzqzqz

Član broj: 66936
Poruke: 218
*.ptt.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 09:20}

Citat:

NrmMyth: logicki nemoguce

koliku brzinu ti zelis???

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

Citat:

cynique: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 ;)

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

Citat:

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

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.

^{04.05.2006. u 09:20}

NrmMyth
Split, Kaštela

Član broj: 63456
Poruke: 839
*.cmu.carnet.hr.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 10:31}

Citat:

qzqzqz: 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...

http://www.last.fm/user/NrmMyth/

^{04.05.2006. u 10:31}

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 185
212.200.10.*

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 12:29}

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...

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

^{04.05.2006. u 12:29}

qzqzqz

Član broj: 66936
Poruke: 218
*.ptt.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{04.05.2006. u 12:38}

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

^{04.05.2006. u 12:38}

ntojzan
Sandor II Tojzan
5digistar Inc.
Kobe city

Član broj: 36657
Poruke: 166
*.bbtec.net.

Sajt: www.5digistar.co.jp

Profil

Re: ispitivanje slozenosti prirodnog broja

^{05.05.2006. u 02:16}

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 * ...

^{05.05.2006. u 02:16}

qzqzqz

Član broj: 66936
Poruke: 218
*.ptt.yu.

Profil

Re: ispitivanje slozenosti prirodnog broja

^{05.05.2006. u 13:49}

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]}

^{05.05.2006. u 13:49}

emiraga

Član broj: 54285
Poruke: 32
217.199.142.*

Profil

Re: ispitivanje slozenosti prirodnog broja

^{05.05.2006. u 22:10}

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

^{05.05.2006. u 22:10}

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 185
212.200.11.*

Profil

Re: ispitivanje slozenosti prirodnog broja

^{11.05.2006. u 01:34}

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....

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

Prikačeni fajlovi

is-prime.pdf - 95.66k

^{11.05.2006. u 01:34}