Primzahlen und Wurzeln?

Hallo,

Ich bin gerade die Laufzeit für das primzahlen Programm zu verbessern Mithilfe der Wurzeln (Math.sqrt) und habe schon viel ausprobiert, aber ich weiß nicht wie und wo ich das genau einsetzen soll. Hier ist erstmal mein Programm, welches ich auch nicht noch viel abändern möchte:

Danke im voraus (:

Answer 1

[ralphdieter]

Deine Schleife läuft bis zahl-1. zahl/2 würde als größter Wert schon reichen und die Geschwindigkeit verdoppeln. sqrt(zahl) ist eine noch bessere Obergrenze (weil nicht beide Faktoren in i·r=zahl größer sein können).

sqrt() liefert aber einen double und ist damit ungenau. Es könnte sein, dass sqrt(n²) eine Zahl ganz knapp unter n ergibt. Du solltest daher lieber etwas großzügig aufrunden. Mit i<=sqrt(zahl)+1 bist Du auf der sicheren Seite.

Comments

[ralphdieter]

Noch ein Tipp: Sobald du erkennst, dass zahl keine Primzahl ist, kannst Du die Schleife mit break abbrechen:

if (zahl%i==0 )
{ 
    primzahl = false;
    break;
}