Alábbi Mersenne prím-kereső algoritmussal mi a hiba? (bővebben lent)
Függvényeket nem én írtam, sokmindent nagybetűvel írtak, amit nem kellett volna.
Egy honlapról vadásztam le.
Hatványokkal gond van, valami fura oknál fogva word típusú változóval nézi az adott szám oszthatóságát és valamiért 2 számtól indulva, így sokkal lassabb, mint lehetne.
SimkoL prímkereső algoritmusát is próbáltam betenni ehelyett, azzal meg jól kiakadt egy idő után...
Mivel a hatványra is butaságokat írogat ki, nem működik jól.
Hatvány kitevőnek magát a számot használja.
program mprimkereso;
var
s, n : int64;
Function Prime(S: Int64): Boolean;
Var J: Word;
Begin
Prime:= False; If S In [0,1] Then Exit;
Prime:= True; If S In [2,3] Then Exit;
Prime:= False; If (S Mod 6<>1) And (S Mod 6<>5) Then Exit;
Prime:= True;
For J:= 2 To S-1 Do If (S Mod J)=0 Then
Begin Prime:= False; Break End;
End;
Function Hatvany(P: Word): Int64;
Begin
If P=0 Then Hatvany:= 1 Else Hatvany:= 2*Hatvany(P-1);
End;
begin
n := 0;
s := 1;
repeat
if prime(hatvany(s)-1) then
begin
writeln(n,'. prímszám: ',s,' hatvány: ',hatvany(s));
inc(n);
end;
inc(s);
until (n = 13);
end.
Főprogramot viszont én írtam és sajnos elfelejtettem helyesen írni, hogy WriteLn :-(
meg egy ReadLn is jó lett volna a végére :-(
válasza:A 6. Mersenne-prím: 524287
A 7. 2147483647
A 8. 2305843009213693951
Úgyhogy ne csodálkozz, hogy kiakad.
Az algoritmus helyesen megtalálja az első 6-ot, utána gondolom túlcsordul a változó.
(Ennél többet ne nagyon várj el.)
A hatvány függvény rekurzívan hívódik, ez is probléma lesz, mert 1, túl nagy értéket vesz fel elég hamar, gondolom emiatt indokolt a word típusú változó.
Másrészt a hívási lánc se mehet túl sokáig.
Amúgy ha Mersenne-prímeket keresel, akkor s csak prím lehet.
Tehát s-et léptethetnéd 3-tól kettesével, illetve mielőtt meghívod a prime(harvany(s)-1)-et, meghívhatod a prime(s)-et is, így kevesebb lesz a fölösleges számolás.
válasza:Szia.
Ez a word-os dolog szerintem a definicióból következik :
[link] :
"A matematikában Mersenne-prímnek nevezzük a kettő-hatványnál eggyel kisebb, azaz a 2n ‒ 1 alakban felírható prímszámokat, ahol n szintén prímszám. A nevüket Marin Mersenne (1588–1648) francia szerzetes, matematikus, fizikus után kapták."
Ebből következik, hogy a fenti programban az n értéke maximum 65536 (Word tipus limit) lehet.
Sok sikert.
üdv.
válasza:"Hatványokkal gond van, valami fura oknál fogva word típusú változóval nézi az adott szám oszthatóságát és valamiért 2 számtól indulva, így sokkal lassabb, mint lehetne. "
Nagy gond nincs vele, mert pont azt cswinálja, amit kell.
Ez egy helyes prím és hatványozó algoritmus.
De persze lecserélhetőek másmilyenre/gyorsabbra.
"Mivel a hatványra is butaságokat írogat ki, nem működik jól. "
Nálam jól működik, csak egy ponton túlcsordul.
Lehet olyan adattípust használni, ami hosszabb számokat is tud tárolni, de az se fog sokat segíteni, nagyon gyorsan növekednek a 2 hatványok, hamar túl fog csordulni.
"Hatvány kitevőnek magát a számot használja. "
Hatvany nevű függvény bekér egy számot 'p'
És rekurzív (szorzó) algoritmussal kiszámolja a 2^p-t.
Tényleges hatványozás nem történik, így nincs értelme kitevőről beszélni.
válasza:A Free Pascal ismeri a QWord típust így el lehet menni a 2^61 - 1 -ig mert ugye 2 és 64 között a 61 a legnagyobb prím. A prím kitevőkhöz Eratoszthenész szitáját tartom a legegyszerűbbnek egy 64 elemű Boolean tömbbel. A prím vizsgálatnál a páros vizsgálat elhagyható mivel nem ellenőrzünk csak páratlan számokat.
válasza:Nagyon köszönöm, érdekes ez az algoritmus.
Kár, hogy én ennyire nem értek hozzá, hogy meg tudtam volna csinálni. :-(
Szitára én is gondoltam, hogy "valamilyen módon be lehetne építeni".
válasza:"Eratoszthenész szitáját tartom a legegyszerűbbnek egy 64 elemű Boolean tömbbel."
A 2^61-1 prím ellenőrzésének az ideje tart sokáig, ahhoz képest minden más elhanyagolható.
Ez a szitálás persze okos dolog, csak gyakorlati haszna nem nagyon van ebben az esetben szerintem.
1-től 64-ig mindegy, hogy szitálsz vagy külön-külön meghívod 3-tól 63-ig a páratlan számokra a prím ellenőrző függvényt.
Azt érdemes lenne megnézni, hogy ha 2^31-enig lennének szitálva a prímek attól gyorsabb lenne-e az ellenőrzés.
De én ezt csak java-ban tudnám implementálni :)
válasza:Igyekszem a válaszaimba mindig valami 'érdekességet' bevinni mint most is ez a szita. Hogy mennyivel jobb, gyorsabb vagy lassabb mintha 30 számra hívnánk egy-egy prímvizsgálatot az szerintem igazából a mai gépek sebessége mellett nem mérhető.
A 2 ^ 31 -ig elmenni a prímszámokkal szerintem eléggé tárigényes, az időről nem is beszélve.
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!