Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Performance bei Primzahltester verbessern
MrChangeLog
myCSharp.de - Member

Avatar #avatar-4086.gif


Dabei seit:
Beiträge: 135

Themenstarter:

Performance bei Primzahltester verbessern

beantworten | zitieren | melden

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
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von MrChangeLog am .
private Nachricht | Beiträge des Benutzers
Cat
myCSharp.de - Member

Avatar #avatar-3070.jpg


Dabei seit:
Beiträge: 790

beantworten | zitieren | melden

Hi,

maximal sqrt(eingabe), d.h.


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

Gib mal 2 bei deinem Programm ein...
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7523
Herkunft: Waidring

beantworten | zitieren | melden

Hallo MrChangeLog,

zuerst zum Code wie er da steht.
Zitat


int nein = 0;
Verwende da besser ein bool. Dazu ist das bool da.
Zitat


    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.
Zitat
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!"
private Nachricht | Beiträge des Benutzers
MrChangeLog
myCSharp.de - Member

Avatar #avatar-4086.gif


Dabei seit:
Beiträge: 135

Themenstarter:

beantworten | zitieren | melden

Danke euch beiden :-)
Zitat von Cat

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!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MrChangeLog am .
private Nachricht | Beiträge des Benutzers
Deaktiviertes Profil
myCSharp.de - Member



Dabei seit:
Beiträge: 996

beantworten | zitieren | melden

Gut, dass man sich bei der Definition "Was ist eine Primzahl" nicht streiten muss:
Zitat
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
private Nachricht | Beiträge des Benutzers

Moderationshinweis von gfoidl (07.02.2017 - 14:37:26):

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