myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Entwicklung » Code-Reviews » Performance bei Primzahltester verbessern
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

Performance bei Primzahltester verbessern

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
MrChangeLog
myCSharp.de-Mitglied

avatar-4086.gif


Dabei seit: 26.07.2016
Beiträge: 121


MrChangeLog ist offline

Performance bei Primzahltester verbessern

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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:

C#-Code:
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 07.02.2017 13:54.

07.02.2017 13:47 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Cat
myCSharp.de-Mitglied

avatar-3070.jpg


Dabei seit: 25.10.2009
Beiträge: 771


Cat ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hi,

maximal sqrt(eingabe), d.h.

C#-Code:
for (int i = 3; i * i <= eingabe; i += 2)

Gib mal 2 bei deinem Programm ein...
07.02.2017 13:59 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
gfoidl gfoidl ist männlich
myCSharp.de-Team

avatar-2894.jpg


Dabei seit: 07.06.2009
Beiträge: 6.673
Entwicklungsumgebung: VS 2019
Herkunft: Waidring


gfoidl ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo MrChangeLog,

zuerst zum Code wie er da steht.

Zitat:
C#-Code:
int nein = 0;

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

Zitat:
C#-Code:
    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

C#-Code:
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ü
07.02.2017 14:03 Beiträge des Benutzers | zu Buddylist hinzufügen
MrChangeLog
myCSharp.de-Mitglied

avatar-4086.gif


Dabei seit: 26.07.2016
Beiträge: 121

Themenstarter Thema begonnen von MrChangeLog

MrChangeLog ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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! Zunge raus

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MrChangeLog am 07.02.2017 14:37.

07.02.2017 14:12 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Deaktiviertes Profil Deaktiviertes Profil ist männlich
myCSharp.de-Mitglied

Dabei seit: 06.07.2014
Beiträge: 985


Deaktiviertes Profil ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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

07.02.2017 14:36 Beiträge des Benutzers | zu Buddylist hinzufügen
myCSharp.de
Moderationshinweis von gfoidl (07.02.2017 14:37):

Genau. Deshalb sollten wir uns hier nicht in der Definition und Sichtweise von Primzahlen verlieren, sondern beim Thema (=hier Code) bleiben.
 
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 3 Jahre.
Der letzte Beitrag ist älter als 3 Jahre.
Antwort erstellen


© Copyright 2003-2020 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 23.11.2020 17:11