Feedback

C# - Primzahl berechnen (optimiert)

Veröffentlicht von am 2/8/2009
(3 Bewertungen)
Angeregt von den Kommentaren des folgenden Snippets http://dotnet-snippets.de/dns/pruefen-ob-eine-zahl-eine-primzahl-ist-SID227.aspx habe ich den optimierten Algorithmus programmiert. Der Code hat folgende Verbesserungen:

1. Sprechenden Funktionsnamen und Kommentar ;)
2. Schleife nur bis zur Wurzel der Testzahl
3. Erhöhen des Zählers um 2
/// <summary>
/// Prüfen auf eine Primzahl. Es werden nur alle ungeraden Zahlen bis zur Würzel der
/// zu prüfenden Zahl getestet.
/// </summary>
/// <param name="Number">Zu prüfende Zahl</param>
/// <returns>True, wenn die Zahl eine Primzahl ist</returns>
/// <see></see>
public static bool IsPrimeNumber(long testNumber)
{
    if (testNumber < 2) return false;

    // 2 explizit testen, da die Schliefe an 3 startet
    if (testNumber % 2 == 0) return false;

    long upperBorder = (long)System.Math.Round(System.Math.Sqrt(testNumber), 0);
    // Alle ungeraden Zahlen bis zur Wurzel prüfen
    for (long i = 3; i <= upperBorder; i = i + 2)
        if (testNumber % i == 0) return false;
    return true;
}

Abgelegt unter Primzahl, Prime Number, Math.

4 Kommentare zum Snippet

Klemens Nanni schrieb am 3/29/2010:
Dasselbe nur schlanker:
public bool is_pr(int n)
{
    for (short i = 3; i <= Math.Sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
   
    return true;
}
Klemens Nanni schrieb am 4/9/2010:
Nochmals schneller:
http://dotnet-snippets.de/dns/effizientere-primzahlpruefung-grosser-zahlen-SID1373.aspx
spreace schrieb am 12/9/2016:
Wenn du 4 eingibst dann spuckt er dir true aus
Koopakiller schrieb am 12/10/2016:
Thomas Code gibt fälschlicherweise für 2 False aus. Und Klemens Code macht noch mehr falsch... (Stichwort: gerade Zahlen)

Von den Fehlern abgesehen, ist Thomas Code deutlich effizienter.
 

Logge dich ein, um hier zu kommentieren!