ntojzan Sandor II Tojzan Becej
Član broj: 36657 Poruke: 168 *.bbtec.net.
|
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 * ...
|