Feedback

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

Veröffentlicht von am 22.09.2006
(11 Bewertungen)
Der Titel sagt alles
GFU-Schulungen  [Anzeige]

XML und .NET Überblick

Um auf dem neuesten Wissensstand zu sein, sollten Sie unser aktuelles ASP .NET Komplett Seminar belegen.
Nach dem Seminar kennen Sie die wichtigsten Strömungen in der Software-Technologie

Visual Studio Team Foundation Server 2017/2015 (TFS) - Komplett 

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 22.09.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 15.10.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 05.11.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 19.01.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!