To je moc dobrý dotaz, na který by se dalo dostatečně odpovědět tak během...dvousemestrálního kurzu, kdybych tomu dostatečně rozuměl
Limity programovacích jazyků jsou nevýznamná miničíslíčka z pohledu toho, na čem se na PG počítá.
Ono hodně záleží na formátu kandidáta.
Zjistit, jestli je nějaké "obecné číslo" prvočíslem je složité. Takže když se kočka projde po klávesnici a pak ji budeš 5 minut čistit a naboucháš 1000 číslic, tak zjistit jestli je to prvočíslo moc neumíme, není na to praktický matematický aparát.
Už dopracování se k tomu, jak celé číslo vypadá, tak je jasné, že poslední číslice ≠0,2,4,5,6,8. Prostě nesmí končit na sudé (proto často vyjádření +1, případně -1), ani na 5.
Ale zjistit dělitele znamená projít všechny až do jeho odmocniny.
Proto se kandidáti generují nějakou formulí.
Mersenne ve formátu 2^n+1 to má "jednoduché" v tom, že násobení dvojkou lze řešit v binárním rozvojem.
Takže 2^18+1 je binárně 1 + počet nul odpovídají mocnině na konci 1.
Podobné je to u GFN, kde b^n+1 se dá zapsat pro n=262144 jako b^(2^18)+1, tedy trochu košatější, ale je v tom vidět tu binární mocninu.
No, a taky chytří matematici v minulosti, kteří rozvíjeli teorii čísel a vůbec jejich zákonitosti, přišli na různé zkratky.
Třeba Lucas, Lehmer a také Riesel.
Zůstal po nich matematický aparát (začínali nebo dělali v době, kdy nebyli počítače) a pak to chytří programátoři natukali.
Proto je na PG používá aplikace LLR, která je zkratkou těchto pánů.
Když někdo hledá prvočísla v různém formátu, využívá již hotových aplikací a zdrojáků jak na sieving, tak faktoring nebo primality test.
EDIT: Ono se to hůř představuje a dobře to ilustruje Numberphille.
Našel jsem k tomu např.
toto videjko
Když si představím kolik času a peněz jsou lidi opravdu darovat do projektů, by to zasluhovalo větší zabezpečení účtu, jen takový návrh. 
)