Feedback
dotnet-snippets.de

C# - Prüfen ob eine Zahl eine Primzahl ist

Veröffentlicht von am 9/22/2006
(11 Bewertungen)
Der Titel sagt alles
bool CheckPrime(int Number)
{
    for (int i = 2; i <= Number - 1; i++)
    {
        if (Number % i == 0) return true;
    }
    return false;
}
Abgelegt unter Primzahl.

4 Kommentare zum Snippet

MacReeg schrieb am 9/22/2006:
Hallo Khartak !

Dein Codesnippet ist wirklich gut. Die Verarbeitungsgeschwindigkeit Deiner Routine kann aber bei genauer Betrachtung der Definitionen einer Primzahl verdoppelt werden. Hier eine Aussage aus Wikipedia :

Mit Ausnahme der Zahl 2 sind alle Primzahlen p ungerade, denn alle größeren geraden Zahlen lassen sich außer durch sich selbst und 1 auch noch (mindestens) durch 2 teilen. Damit hat jede Primzahl außer 2 die Form 2k + 1 mit einer natürlichen Zahl k.

Das heißt, dass alle Zahlenbereiche über Number/2 keine Teiler der vermutlichen Primzahl (Number) sein können. Durch die Änderung der Bedingung in der for-Schleife auf i < (int)(Number / 2) erhöht sich die Verarbeitungsgeschwindigkeit um den Faktor 2.

Gruß Ernst

Web: http://www.inc-x.de
Email: info@inc-x.de
Borg schrieb am 10/15/2006:
Hi Khartak,
zusätzlich zu dem, was MacReeg schrieb, brauchst du noch weniger Zahlen zu prüfen.
So brauchst du alle Vielfache von bereits getesten Zahlen nicht testen. Dies benötigt allerdings eine Liste (siehe Sieb des Eratosthenes), was zu mehr Speicherplatz führt, allerdings die Laufzeit deutlich verringert. Und bei großen Zahlen fällt diese mehr ins Gewicht. Siehe dazu das Snippet PrimeNumberGenerator.
Ronald schrieb am 11/5/2006:
Hallo,

auch meinen Senf kommt hinzu :)
was gesagt wurde stimmt bereits, aber was man noch vereinfachen könnten wäre in der funktion ZUERST prüfen ob die zahl gerade ist (mit Mod Operator). Falls ja kann abgebrochen werden -> keine Primzahl. Durch diese Anwendung kann die Forschleife auch gekürzt werden indem man bei 3 begint und i+=2 macht (jede ungerade zahl).

Weiters kann ich nur eine "behauptung" sagen, mir wurde durch ein Lehrer gesagt, dass man nur bis Wurzel(testZahl) gehen muss. ich kann nur bezeugen, dass bei mir jetzt alle Primzahlen mit dieser Anwendung gefunden werden.

lg
Shagrath LaVey schrieb am 1/19/2010:
Dass man bis Number/2 prüfen sollte, ist eine beliebte Halbwahrheit. ;-)
Es reicht bis zur sqrt(Number) zu prüfen. Das bringt nochmal ordentlich Performance.
Wenn ich eine Zahl in zwei Faktoren zerlegen möchte, ist einer dieser Faktoren immer kleiner als die Wurzel der Zahl (oder beide Faktoren sind eben exakt die Wurzel).
 

Logge dich ein, um hier zu kommentieren!

Ähnliche Snippets

Suche

Letzte Kommentare

  • Community