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]

VB.NET Aufbau

Sie verfügen nach der Schulung über fundierte Kenntnisse in der Arbeit mit objektorientierten Modellen in VB.NET und können wiederverwendbare Komponenten eigenständig erzeugen.

ASP.NET Core Server- und Client-Programmierung

Sie  lernen in drei (3) Tagen wie man mit  ASP.NET Core und den Technologien  MVC, Entity Framework, WebAPI und  Razor professionelle sowie moderne  Web-Anwendungsarchitekturen aufbaut.  Die Schulung ist der perfekte  Einstieg um insbesondere datengetriebene  und präsentationsorientierte  Applikationen auf Basis der robusten und  skalierbaren ASP.NET Core  Plattform zu erstellen. Nach der Veranstaltung kennen Sie die Konzepte von Angular und können Angular in neue und bestehende ASP.NET-Anwendungen einsetzen.

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!