Willkommen bei dotnet-snippets.de! Snippet hinzufügen Login Registrieren
Snippets in der Datenbank: 1563 | Anzahl registrierter User: 1895 | Besucher online: 1
Hauptmenü
Home
Top Ten
Zufälliger Snippet
FAQs
.NET Community
dotnet-forum.de
dotnet-kicks.de
Social

RSS Feeds
Rss Alle Snippets
Rss C#
Rss VB.NET
Rss C++
Rss ASP.NET
Partner
Member of Microsoft Community Leader/Insider Program (CLIP)

Prüfen ob eine Zahl eine Primzahl ist


Autor: Tim Hartwig
Sprache: C#
 Bewertung:
3.24 (10 votes)
 Anzahl der Aufrufe: 14632
  
Kick it on dotnet-kicks.de  

Beschreibung:

Der Titel sagt alles

Abgelegt unter: Primzahl.


C# 
1
2
3
4
5
6
7
8

bool CheckPrime(int Number)
{
    for (int i = 2; i <= Number - 1; i++)
    {
        if (Number % i == 0) return true;
    }
    return false;
}
Sie haben Fragen zu diesem Snippet oder brauchen Hilfe bei der .NET Entwicklung?
Freundliche und kompetente Entwickler helfen Ihnen gern weiter im Forum für .NET Entwicklung.



Kommentare:
(Zum Schreiben von Kommentaren bitte anmelden.)

MacReeg schrieb am:  22.09.2006 21:33:10

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 02:45:21

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 20:54:03

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 23:59:08

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).


schlecht sehr gut
1 2 3 4 5 6 7 8 9 10
Nur angemeldete User können Snippets bewerten.

Impressum | Kontakt