Laden...

Performance bei Primzahltester verbessern

Erstellt von MrChangeLog vor 7 Jahren Letzter Beitrag vor 7 Jahren 3.950 Views
MrChangeLog Themenstarter:in
121 Beiträge seit 2016
vor 7 Jahren
Performance bei Primzahltester verbessern

Ich habe vor einiger Zeit einmal aus langeweile einen Primzahltester geschrieben. Es handelt sich um ein kleines Konsolenprogramm, bei dem der User eine Zahl eingibt und dann ausgegeben wird, ob es sich um eine Primzahl handelt oder nicht.

Das ganze sieht so aus:


int nein = 0;

if(eingabe%2 == 0)
{
    Console.WriteLine("keine Primzahl");
}
else 
{
    for (int i = 3;i < eingabe / 3; i += 2)
    {
        if (eingabe % i == 0)
        {
            nein = 1;
            break;
        }
    }

    if(nein == 1)
    {
        Console.WriteLine("keine Primzahl");
    }
    else
    {
        Console.WriteLine("Primzahl!");
    }
}

'eingabe' ist die Zahl, die der User eingegeben hat.
Ich möchte das Programm möglichst performant machen und frage mich, wie hoch ich die Grenze (hier 'i < eingabe / 3') ansetzen soll.

Meine Überlegungen: der grösste Teiler einer Zahl kann (wenn man von der Zahl selbst absieht) maximal die Hälfte der besagten Zahl sein - natürlich nur dann, wenn diese Zahl gerade ist. Mit meinem if teste ich nun bereits, ob die Zahl gerade ist oder nicht (weswegen ich in der for-Schleife auch nur ungerade Zahlen teste). Daher wäre 'eingabe / 2' als Grenze höher als notwendig.

Das Problem (bei ungerader Zahl):
wenn eingabe % 3 != 0, dann liegt die Grenze unter eingabe / 3
wenn eingabe % 5 != 0, dann liegt die Grenze unter eingabe / 5
wenn eingabe % 7 != 0, dann liegt die Grenze unter eingabe / 7

und so weiter ...

Kennt einer von euch ne vernünftige Lösung für das Problem?

Edit: Schreibfehler korrigiert

771 Beiträge seit 2009
vor 7 Jahren

Hi,

maximal sqrt(eingabe), d.h.


for (int i = 3; i * i <= eingabe; i += 2)

Gib mal 2 bei deinem Programm ein...

6.911 Beiträge seit 2009
vor 7 Jahren

Hallo MrChangeLog,

zuerst zum Code wie er da steht.

  
int nein = 0;  
  

Verwende da besser ein bool. Dazu ist das bool da.

  
    if(nein = 1)  
    {  
        Console.WriteLine("keine Primzahl");  
    }  
    else  
    {  
        Console.WriteLine("Primzahl!");  
    }  
  

Lässt sich so nicht kompilieren, da der Vergleich mit == stattfinden muss. So wäre das eine Zuweisung und diese ist im if-Ausdruck nicht gestattet.

Mit dem bool könnte dies außerdem zu


Console.WriteLine("{0} Primzahl", isPrime ? "" : "keine ");

verkürzt werden.

Außerdem würde ich die Logik in eine eigene Methode mit Rückgabewert bool packen und so die Consolen.Ausgabe in dieser Methode raushalten.

frage mich, wie hoch ich die Grenze

Angenommen n ist die zu prüfende Zahl, so kann beim Sieb des Eratosthenes als Grenze sqrt(n) genommen werden (Begründung liegt in der Faktorenzerlegung).

Die bereits berechneten Ergebnisse kannst du dir merken (Memoization) und dann genügt für ein bereits geprüfte Eingabe ein Lookup -> also Speichern der Ergebnisse in einem Dictionary<Eingabe, Primzahl ja/nein>

Es gibt auch alternative Primzahltests wie den von Fermat, Miller-Rabin. Diese sind oft wesentlich schneller, da direktere Berechnungen erfolgen, aber liefern z.T. keine 100% sicheren Ergebnisse.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

MrChangeLog Themenstarter:in
121 Beiträge seit 2016
vor 7 Jahren

Danke euch beiden 🙂

Gib mal 2 bei deinem Programm ein...

Ja ich weiss, 2 wird auch als Primzahl angesehen. Da die 2 aber eine gerade Zahl ist weigere ich mich, sie als Primzahl zu akzeptieren!
Hmpf! 😜

D
985 Beiträge seit 2014
vor 7 Jahren

Gut, dass man sich bei der Definition "Was ist eine Primzahl" nicht streiten muss:

Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist. Eine Primzahl ist also eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat

Hinweis von gfoidl vor 7 Jahren

Genau. Deshalb sollten wir uns hier nicht in der Definition und Sichtweise von Primzahlen verlieren, sondern beim Thema (=hier Code) bleiben.