A Fermat-teszt helyett mindenképp a másik két teszt valamelyikét használd szerintem. (Főleg ha fontos számodra, hogy melyik (hanyadik) prímről van szó.)
Mikor elég ,,biztos'', hogy prím egy szám? Engem meggyőzne, ha 2^{-300}-nál kisebb valószínűséggel összetett egy szám. :)
Érdemes lehet megnézni, hogy milyen számrendszert használ belül a GMP és arra optimalizálni. (Úgy rémlik, hogy valamilyen (ezer és millió közti) (2-hatvány +/- 1) prím alapú. Ez persze csak régi emlékeim felidézése.)
100 000 szám azért elég ritkásan van 2^256-ig... Úgyhogy rettentő sokat kell majd számolnod annak meghatározásához, hogy megtudd melyik prímet találtad meg. (Ha jól számoltam, akkor kb. 2^253 prím van addig. Ahhoz képest jókora lyukak lesznek a számok között.)
(Az algoritmusodról nem mondanék véleményt... Most túl fáradt vagyok, de lehet, hogy holnap alaposabban elemzem.)