Melyik a leggyorsabb prímszámvizsgáló algoritmus?

ha leggyorsabb vizsgálatot akarod, akkor gépi kódot ajánlom. a többi nyelv baromi lassú hozzá képest.

mellesleg ha az algoritmus funkció blokkdiagramját fel tudod vázolni, akkor már nyertél.

[link]

A megadott nyelvek közül én a C++ -t ajánlanám, ha esetleg van tapasztalat, akkor assembly-ben lenne a legideálisabb megírni (persze sokkal bonyolultabb megírni ASM-ben)

Eratosthenes szitája gyorsan keres egy intervallumban prím számokat.

Prímtesztnek meg csak annyit tudok mondani, hogy a szám gyökéig kell keresni osztokat, ha van akkor nem primszám,

ha nincs akkor prímszám.

[link]

Az Eratosztenészi szita csak az [1, x] intervallumokban tud prímet keresni.

Egyéb prímtesztek:

[link]

Az Eratosztenészi-szita amúgy tényleg nagyon gyors, kb. Ln(ln(x))*x-es futásidejű, viszont akkor

1) mivel 10^50-es nagyságrendről van szó, a futásidő is hasonló lesz

2) kb. 2^130 Gb memória kéne a számok tárolásához.

A Miller-Rabin teszt sokkal jobb, mert egy számot log(x) idő alatt ellenőriz, ez n számra n*log(x), ez lassabb, mint az eratosztenészi, de itt n nem 10^50, hanem szabadon választott, tehát ha 20000 számot kell megnézni, akkor 20000*log(x)-es. Ez pedig bőven belefér akár pár percbe is. Másrészt nagyon kevés memóriát igényel.