Feedback

Primzahl berechnen (optimiert)

C# - ThomasMentzel Februar 8, 2009
3 Ratings 2.8333/5

Sprache: C#

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;
}

/// <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 Math Prime Number Primzahl

Alte URL: /snippet/primzahl-berechnen-optimiert/1075

4 Kommentare

  1. Dasselbe nur schlanker:
    [code]public bool is_pr(int n)
    {
        for (short i = 3; i <= Math.Sqrt(n); i += 2) {         if (n % i == 0) return false;     }         return true; } [/code]

  4. 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.