Feedback

C# - Primzahl berechnen (optimiert)

Veröffentlicht von am 08.02.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
GFU-Schulungen  [Anzeige]

ASP.NET 2.0 und 3.5

Dieser Kurs vermittelt Ihnen alle Erweiterungen von Microsoft ASP.NET 2.0. Zu diesen zählen u. a. Data Bindung, Master Pages, und Security.

VB.NET Aufbau

Sie verfügen nach der Schulung über fundierte Kenntnisse in der Arbeit mit objektorientierten Modellen in VB.NET und können wiederverwendbare Komponenten eigenständig erzeugen.

/// <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 29.03.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 09.04.2010:
Nochmals schneller:
http://dotnet-snippets.de/dns/effizientere-primzahlpruefung-grosser-zahlen-SID1373.aspx
spreace schrieb am 09.12.2016:
Wenn du 4 eingibst dann spuckt er dir true aus
Koopakiller schrieb am 10.12.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!