bhè, intanto, non serve affatto fino alla metà, ma basta fino alla radice quadrata (perchè?).

Un metodo storico è il crivello di Eratostene, ma non fa di certo al caso tuo.

Puoi leggere un po' di roba qui:

http://mathworld.wolfram.com/PrimeNumber.html

Oppure cercare "Mersenne" in google, dovrebbe uscirti, tra i primi risultati, il più grande progetto di ricerca di grandi primi.
Divertiti.