Aaaaaaalso: Ich will nicht zwei Tonnen Code zusammensammeln und dann posten, also frag ich dich hier erstmal nach ner genaueren Klassifizierung deines Problems:

Für größere Zahlen'bereiche' dh. mehrere aufeinanderfolgende Zahlen auf Primität zu testen, ist das von EB präsentierte Sieb am schnellsten (wobei es reicht das Sieb mit Primzahlen durchzuführen).

dieser Test sollte für alle 'kleinen' Primzahlen verwendet werden. Klein heißt in diesem Fall kleiner als ne Milliarde oder so.

Wenn du von einer Zahl mit über 95% Wahrscheinlichkeit prim haben willst, dann ist ein einfacher Fermattest am schnellsten.

Wenn du ne Zahl mit beliebig großer Wahrscheinlichkeit prim haben willst, dann ist der Miller-Rabin-Test am schnellsten.

Wenn du ne Zahl definitiv prim haben willst, dann ist der AKS bei über 20000bit am schnellsten. Was unter 20000 bit am schnellsten ist, weiß ich nicht genau (müßte nachschauen).

Wenn du einfach nur ne große Primzahl haben willst, aber nicht von einer Zahl wissen willst, ob sie prim ist, dann ist der von EB erwähnte, von mir programmierte Algo am schnellsten.

Alle Angaben ohne Gewähr auf Algorithmen, die ich nicht kenne, sollte aber nicht so viele sein..

ps:
merkt man, daß du damit eins meiner Lieblingsthemen genau erwischt hast?