Na először is prímellenőrzés:
Megnézzük, hogy kis számokkal osztható-e. Kb 13-ig minden számra ismert valami összefüggés, olyasmi, mint tizes számrendszerben ha a számjegyek összege osztható 3-mal akkor a szám is osztható.
Ez konkrétan igaz (ha jól számolom) 16-os számrendszerben a 3-ra és az 5-re is (9-re viszont nem).
Ezek marha gyors tesztek (gyorsabb mintha tényleg leosztanál), kiszórnak egy csomó számot.
Ezután jönnek a valószínüségi tesztek, mint pl a Fermat teszt:
1 < a < m, ekkor ha
a^(m-1) mod m <> 1, akkor m összetett.
Ez azért jó, mert minden prímre az eredmény 1, és bár van olyan összetett szám, amire szintén 1, de viszonylag kevés.
És ez relatív könnyen számítható (bár ez első pillantásra nem biztos, hogy látszik :) ).
Ezeknek a teszteknek az az értelme, hogy minden teszt amin átment a szám, egyre inkább növeli annak a valószínüségét, hogy prímszám, miközben sokkal gyorsabbak, mint egy teljes prímteszt.
RSA kódolásnál pl meg is elégednek ennyivel (sőt eleve nem random kulcsot, hanem konkrét alakú számokat vizsgálnak (mint a mersenne félék, de persze konkrétan nem azokat)). Mert még ha nem is prímeket generált, nagyon kicsi az esélye, hogy nem működik a titkosítás.
Ha neked biztos eredmény kell, ezekután még mindig jöhet valami teljes prímteszt, szerintem a faktorizációnál biztos van gyorsabb is.
Ilyen tesztekről olvashatsz itt http://compalg.inf.elte.hu/~ajarai/konyvek.html a "Számítógépes számelmélet" című könyvben. Nem állítom, hogy ebből meg fogod érteni, de legalább tudod, hogy mit kell keresned a neten.
Ami még kötelező az a D. E. Knut könyvének (The Art of Computer Programming) 2. része (Seminumerical algorithms). Ez megjelent már magyarul is.
"ill. sokkal fontosabb az, hogy hanyadik primet kaptam vissza a sorozatbol 2-vel kezdodoen."
Na erre nincs ötletem, bár erre a faktorizáció sem megoldás.
Erre egyébként a Nagy prímszámtétel ad egy elég jó becslést n/log n alakban. Konkrét (hatékony) algoritmusról még nem hallottam.
Szerk:
Legközelebb előbb keresek és aztán írok...
Kb. minden amiről eddig a számat téptem:
http://en.wikipedia.org/wiki/Primality_test
Kellemes olvasgatást...