Prímszámok keresése, tesztelése?
Olvasgattam, hogy vannak módszerek prímszámok keresésére. Tehát nem kell végigpróbálni egy nagyobb szám esetén az összes nála kisebb prímszámot.
Tudna nekem valaki ilyen tesztet ajánlani? Illetve le tudná nekem konyha nyelven, érthetően írni? Amiket eddig láttam, azokat nehezen tudom értelmezni.
Végül is egy algorimus megírása lenne a cél.
válasza:Indiai matematikusok találtak olyan algoritmust, ami "P-ben van", vagyis írható rá olyan algoritmus, melynek a lefutási ideje jellemezhető egy polinommal; például, ha egy algoritmus lépésszámára adható felső becslés n^1000, ahol n a feldolgozandó adatok összessége, ez az algoritmus "gyorsnak" mondható. "Lassú" algoritmusnak nevezzük, ha 2^n felső becslés adható a lépésszámra (mivel a 2^n egy irdatlanul gyorsan növő függvény, így sok lépés kell a lefutásra nagy n-re).
Az indiai algoritmus ezzel szemben mégsem hatékony, csak olyan számokra "spórolja meg" a lépéssszámot, aminek esetleg nincs gyakorlati haszna (tehát rohadt nagy számokra éri meg lefuttatni, kisebb számoknál jobban jársz, ha végigpróbálod az összes alatta lévő számot).
Egy nagyon egyszerű szabály azt mondja ki, hogy nem kell az összes, a számnál kisebb számmal végigosztani a számot, elég a gyökéig, például, ha azt akarjuk megtudni, hogy a 161 prímszám-e, akkor csak gyök(161)=12,68-ig, vagyis 1-től 12-ig kell csak elosztani a számot. Ha kapunk egész eredményt, akkor nem prím, ha nem akkor igen.
Remélem érthető :)
Köszönöm a válaszokat! A gyökös dologra én is rájöttem. Illetve, az magától értetődő, hogy elég csak 1db osztót találni 1-en és önmagán kívül. Ez a 2 dolog megvan, van is rá algoritmusom, tűrhető sebességgel is dolgozik milliós nagyságrendű számokkal is.
Igazából ami engem érdekelne azok ezek a képletek lennének:
Azt szeretném megérteni, hogy milyen elven működnek.
Illetve, ha bármelyiket konyhai nyelven le tudná írni valaki, hogy hogyan működnek, akkor annak örülnék.
(mod n) például nem tudom értelmezni, maradék?
válasza:A "három vonalas egyenlőségjel" a kongruenciát jelenti, és így szokták használni:
x(kongruens)=y mod(z)
Ez azt jelenti (konyhanyelven), hogy ha x-et és y-t elosztjuk maradékosan z-vel, akkor mindig ugyanazt a maradékot kapjuk, például:
2(kongruens)=8 mod(3), mivel
2:3=0, maradék 2
8:3=2, maradék 2, és mivel a maradékok megegyeznek, ezért ezek kongruensek egymással, ha a modulus (maradékosztály) a 3.
Köszönöm, így már a Kis Fermat-tételt értelmeztem is! Az algoritmust is megcsináltam. Az hiszem csak a 341 számot hibázta el ahogy írták is.
Ennek a képletnek a fő hibája az, hogy a prím számnak hatványkitevőként kell szerepelnie, majd a borzalmas nagy számból kell osztási maradékot számolni.
1000 feletti számoknál már alig döcög az algoritmus.
válasza:A gyakorlatban nem számolnak borzalmas nagy számokkal.
Nem úgy számolják ki, hogy először a hatvány értékét, majd abból a maradékot, hanem moduláris hatványozással.
Erre keress rá, ill. olvasd el ezt:
válasza:A (2) Számelmélet rész "nulláról" magyarázza, pár oldal után a prímtesztekhez is eljutsz.
Viszont az "új" biztos, polinomiális prímteszt nincsen benne.
Köszönöm a válaszokat! A moduláris hatványozás elvét is megértettem, ebből a példából:
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
De ha nagyobb számokra szeretném használni akkor bajban vagyok:
n=123456789
x=2^(123456789-1) mod 123456789
x=2^123456788 mod 123456789 = (2^100 mod n ^ 1234567 * 2^88 mod n) mod n
Nyilván az lenne a jó, ha " 2^100 mod n " minél kisebb szám lenne.
Hogyan tudnám ezt az egyenletet szépen megoldani, leegyszerűsíteni? Akár több lépésben is for ciklussal?
válasza:Nem igazán nézted meg, mert találtál volna algoritmusokat dögivel, pl:
r = a^e (mod m).
modhatv(a, e, m) ; a=2, e=123456788, m=123456789
r = 1;
while[amíg] (e > 0) do[csináld]
... if[ha] (e mod 2 <> 0) then[akkor] r = (r * a) mod m;
... a = (a * a) mod m;
... e = e div 2;
return r;
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!