Új prímszámok kiszámolása

Az Eratoszthenész szitája módszerrel lehetőség van a prímszámok kiszűrésére a számok közül. Sajnos nagyobb prímszámok esetén papíron elég nehézkes a módszer, inkább számítógéppel érdemes végezni.

1. Írd fel a számokat 2-től addig, amíg tesztelni akarod a számokat! Ez az első lista.
2. A második listádra írd fel a 2-t, ami az első prímszám!
3. Az első listáról húzd le 2-t, és az összes többszörösét!
4. Az első át nem húzott szám a következő prím. Írd fel a második listára, és folytasd ezzel a számmal a 3. ponttól mindaddig, amíg az első listán nem húztad át az összes számot!

A második listán lesznek a prímek kigyűjtve.

(Az eredeti itt lévő cikkben rossz módszer volt felírva, ezért javítva lett.)

Feca2010. febr.

Hiba jelentéseHiba jelentése

Kapcsolódó trükkök

Összes trükk

Hozzászólások

Hozzászólás írásához jelentkezz be vagy lépj be Facebookkal!

Attei

sizeref, vannak felhőszolgáltatások, pl. az Amazonnak, amiknél programod tetszőleges erőforrást használhat, akár több ezer gépet is, és a használat után kell fizetni. Ez például segíthet, de nem lesz olcsó, az algoritmus optimalizálásával lehet hogy jobb eredményt érsz el, illetve vannak a neten prímadatbázisok is, ha csak az eredmény kellene... :)

sizeref

Igazából segítséget szeretnék kérni. Van egy algoritmusom, mely az adott számról megmondja: prím szám -e, ikerprím-e, illetve ha nem prím mik az osztói. Azonban az asztali gép lehetőségeit kinőttem. A környezetemben nem találok segítséget. Kinek milyen ötlete van a "hogyan tovább".

kissgdr

A fenti módszer alapvetően annak bizonyítására szolgál, hogy végtelen sok prímszám van (azaz nincs köztük legnagyobb).
Tegyük fel, hogy véges sok prímszám van. Akkor ezeknek szorzata +1 szintén prímszám lenne, ugyanis nem osztható egyik előző prímmel sem. Az ellentmondást a kiinduló feltételezés okozza. Prímszám generálására a fenti módszer alkalmatlan.

 

wrot

A módszer jó, a leírás rossz.
Megpróbálom helyesen leírni:
  szorozzuk össze az összes ismert prímet
  adjunk hozzá egyet
  beláthatjuk, hogy kapott szám nem osztható egyik tényezővel sem,
  ezért:
           vagy a kapott szám prím,            vagy a prímtényezős felbontásában találunk új prímet.

Pl1.: ismert prímek: 2, 3, 5.
      2*3*5+1=31   (a 31 prím)
Pl2.: ismert prímek:2, 3, 5, 7, 11, 13
      2*3*5*7*11*13+1=30031  (=59*509, ahol 2 új prímet találtunk)

d-nash

Kedves Szerző!

A módszer nem jó, mert az így előállított számok nem mind prímek. Itt egy ellenpélda:
2×3×5×7×11×13 + 1 = 30031 = 59×509, tehát a 30031 nem prím.

Üdv,
Dénes

mkrisz237

Üdv!
hu3b1129-nek igazat kell adnom, mert 2-nek a 4. hatványa 16. 16-1=15=3*5, tehát nem prímszám

hu3b1129

@csernus:  A lenti állításod sajnos nem igaz.

Például a 11 prím, de 2^11 − 1 = 2047 = 23 × 89,

vagy például a 29 prím, de 2^29-1=536870911 = 233 x 1103 x 2089.


Igazából még azt sem tudjuk, hogy van-e végtelen sok 2^p-1 alakú (a szakirodalomban Mersenne-prímeknek nevezett) prímszám, ahol p maga is prím.

csernus

Ennél van egy szerintem jobb módszer is. Fogsz egy prímszámot, p-t. Fogod a 2-t, p hatványára emeled, majd kivonsz 1-et az eredményből. Az eredmény biztos, hogy mindig prím lesz.
Pl.: p=13
2 a 13. hatványon=8192
Tehát a 8191 biztosan prím szám lesz.
Ezzel a módszerrel könnyebb dolgozni és számolni is, hiszen csak 1 prím számot kell ismerni, viszont hátránya, hogy nagyon nagy számokat fogunk kapni. Ezeket a számokat nevezzük Mersenne prímeknek, és a világ legnagyobb prímjeit keresik ezzel a módszerrel.

ipi

Mi a prímszám?
Röviden: Aminek pontosan két osztója van.

hu3b1129

A prímszám definíciója: olyan egységtől különböző p egész szám, amire teljesül, hogy minden esetben amikor p osztója az AxB szorzatnak, akkor a p osztója A-nak, illetve p osztója B-nek feltételek közül legalább az egyik teljesül. Az egységet azért kell kizárni a prímek köréből, hogy igaz legyen az egész számok egyértelmű faktorizációs tétele, azaz hogy minden egységtől és 0-tól különböző egész szám egyértelműen felírható legyen prímhatványok szorzataként.