nicht angemeldet
Hallo Éner,
Ok, Du probierst einfach alle Zahlen die kleiner als die Wurzel sind als mögliche Teiler durch. Das ist ungefähr die langsamste Methode.
Guck Dir mal http://de.wikipedia.org/wiki/Primzahltest an.
Ich würde versuchen einen randomisierten, schnellen Test zu verwenden (Miller-Rabin z.B.) und damit erstmal die Zahl der Kandidaten deutlich zu reduzieren. Da diese Tests Fehler machen, muss man dann noch einen langsameren Test nachschalten. Irgend ein verbesserter Fermat-Test bietet sich da an.
Grüße
Daniel