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

Régen az emberek azt hitték, hogy a prímszámok között is van legnagyobb, legutolsó. Nos tévedtek, van egy egyszerű szabály az új prímszám megállapítására:
Először is ismerned kell a alapvető prímeket: 2, 3, 5, 7, 11, 13, 17, ...
Szorozd össze sorra a prímszámokat majd adj hozzá 1-et. Mivel a szám létrehozásának módjából látható, hogy az összeszorzott prímszámok egyikével sem osztható (a maradék 1), ezért ez is prímszám lesz.
Ezzel nem tudod megállapítani az összes prímet, pl. az 5-öt, 11-et, 13-at és még sok más prímet sem, de a kapott szám mindig prím lesz.

Példák:
2+1=3
2*3+1=7
2*3*5+1=31
2*3*5*7+1=211
2*3*5*7*11+1=2311

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!

Atteijan. 19.

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.