Fórum: Marsenne-prímek

Ha már a Mersenne-prímek akkor itt egy friss infó:

http://mathworld.wolfram.com/news/2006-09-04/mersenne-44/

Amúgy, ha nem megy átírni C-be (amit azért kétlek, mert nem hiszem, hogy nehéz megérteni egy programozási nyelvet, ha ismersz már legalább 1-et), akkor megpróbálhatom én is, mert írtam már C-ben programot, csak nem akartam hogy kinevessenek az esetleges hibáim miatt, amik úgyis lennének... :)

Egyébként valóban egyszerű a program, én arra gondoltam, hogy a 2^k-1-es maradék vizsgálatát külön meg akarod írni (azzal kicsit bonyolultabb lenne), ezért írtam a megjegyzést a program után. Egyébként 2-es számrendszerben nyilván a számot k-s blokkokra kell szedni és ezeket k-jegyű számokként összegezve adódik a 2^k-1-es maradék.

Persze, az if (b=0) ellenőrzi

Igen, a longint már a 17-es kitevő vizsgálatakor átcsap negatívba. :(

kösz, megpróbálom átírni cbe, már amennyire értem a pascalt azt hittem kicsit bonyolultabb lesz a forráskód és itt le is van ellenőrizve, hogy Mp| ap-1 ?

Mellesleg a Pascal longint-je nem kifejezetten nagy számokra találtatott ki, de ez van :) Viszont Java-ban a BigInt már egész szép...

Program: a p kitevőjű Mersenne-számról kideríti, hogy prím-e

program mersenne; var a,b: longint; p,i,j: integer; begin

readln(p);

a:=1;

for i:=1 to p do begin a:=a*2; end;

a:=a-1;

b:=4;

for j:=2 to p-1 do begin b:=((b*b-2) mod a); end;

if b=0 then writeln('a ',p,'. Mersenne-szám prím'); readln;

end.

Igazából a ((b*b-2) mod a) részről írja a cikk, hogy igen gyorsan elvégezhető számítási művelet, viszont jó kérdés, hogy Pascal vagy C szinten is valóban gyors-e, vagy érdemes külön megírni valami alacsony szintű programozási nyelven azt a részt.

Jó, akkor mondjuk Pascal

Tényleg elírtam bocs. Persze más is megfelel. Ha van kedved és időd akkor örülnék neki. Előre is köszönöm.

Most látom, hogy elírtad a topik nevét. Amúgy, nem vállalkozom, hogy C-ben leírom a programot, mert nem igen használom ezt a nyelvet, de ha valamelyik másik megfelel, akkor megpróbálhatom.

A cikkben a legkisebb abszolútértékű maradékokat tüntették fel, a₃=194=127+67=2^.127-60, tehát a₃=19467-60(127), hasonlóan a többi példánál.

Elős felét értem, köszönöm. Gondolom megnézted a tétel után lévő példát. Meg tudod nekem magyarázni, hogyan jöttek ki? a1 és a2 világos, de utána nem működik a an+1=an2-2 rekurzió. Ötlet?

Az a|b azt jelenti, hogy a osztója b-nek. Az

ab  (m)

nem azonos egyenlőséget, hanem kongruenciát jelöl.

ab  (m)

vagy

ab  (mod  m)

(ejtsd a kongruens b modulo m) azt jelenti, hogy m|(a-b).

Tisztelt "Matek-szeretők"! Előre is bocsánatot kérek, hogy új topikot nyitottam. Mondjuk úgy, hogy én egy lelkes amatőr vagyok. Borzasztóan érdekelnek a Marsenne prímek, csak épp egy érettségivel még hozzáfogni is szinte lehetetlen. Tulajdonképpen, csak a Lucas tétel(1876) lenne érdekes. Az, hogy hogyan tudom megmondani egy számról, hogy prím-e, anélkül, hogy a gyökéig elosztanám az összes egész számmal. Tudom ,hogy a 2-t kivéve a páros számokat ki lehet hagyni, a 3on kívűl az összes 3al oszthatót, és az 5re végződőeket stb. Illetve elég lenne a gyökéig található prímekkel elosztani, csak ehhez ismerni kéne addig az összes prímet, ami elég nehézkes nagyobb számoknál.

A tétel(bár gondolom sokan ismerik): http://komal.elte.hu/cikkek/2004-02/freud.h.shtml

Többször átnéztem a példát itt is és más helyeken is, de van pár dolog, amit nem értek: 1., Mit jelent a következő jel: | (alt+w) ? 2., Mi a különbség az egyenlő és az azonosan egyenlő közt? 3., Mit jelent a konkrét példában a harmadik tagtól a (mod 127), és azt sem értem, hogyan lesz a 3. tag -60.

Ha van valakinek egy kis ideje, nagyon szépen megköszönném ha segítene. Elvégre Einstein is megbukott matekból :)

És ha esetleg a tétel alapján lenne valakinek egy c-nyelvű forráskódja, amivel ezt a tesztet adott számon el lehetne végezni, annak is örülnék. Tulajdonképpen ez alapján akartam egy prímkereső algoritmust írni, csak az alapoknál elakadtam.

Köszönettel: river40