Programm zum finden von Primzahlen
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich möchte zu finden, die prime Zahl zwischen 0 und einer long-Variablen, aber ich bin nicht in der Lage zu bekommen jede Ausgabe.
Das Programm ist
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
Kann einer mir helfen und herauszufinden, was die möglichen Fehler im Programm?
Lösung
Sie können dies schneller tun, um eine fast optimal Probedivision Sieb in einer (langen) Zeile wie diese verwenden:
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
Die Näherungsformel für die Anzahl der Primzahlen hier verwendet wird, ist π(x) < 1.26 x / ln(x) . Wir brauchen nur von Primzahlen nicht größer als x = sqrt(num) .
Beachten Sie, dass die Sieb des Eratosthenes hat viel bessere Laufzeitkomplexität als Probedivision (laufen soll viel schneller für größere num Werte, wenn sie richtig umgesetzt).
Andere Tipps
Versuchen Sie folgendes:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
Sie müssen nur ungerade Teiler bis zur Quadratwurzel der Anzahl überprüfen. Mit anderen Worten braucht Ihre innere Schleife zu starten:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
Sie können auch so schnell aus der Funktion brechen, wie Sie die Zahl nicht prim finden, Sie brauchen keine mehr Teilern zu überprüfen (ich sehe Sie schon das zu tun!).
Dies funktioniert nur, wenn num größer als zwei ist.
Nein Sqrt
Sie können die Sqrt ganz vermeiden, indem eine laufende Summe zu halten. Zum Beispiel:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
Das ist, weil die Summe der Zahlen 1 + (3 + 5) + (7 + 9) Ihnen eine Folge von ungeraden Quadraten geben (1,9,25 usw.). Und daher stellt j die Quadratwurzel square_sum. Solange square_sum weniger als i dann j kleiner ist als die Quadratwurzel.
Leute haben erwähnt, ein paar von den Bausteinen zu tun diese effizient, aber niemand ist wirklich setzen Sie die Stücke zusammen.Die Sieb des Eratosthenes ein guter Anfang ist, aber mit ihm werden Sie run out of memory lange bevor Sie erreichen Sie das limit festgelegt haben.Das bedeutet nicht, es ist sinnlos, obwohl-wenn Sie Ihre Schleife, was Sie wirklich über Primzahlen sind Teiler.Als solche, Sie können beginnen, indem Sie mit dem Sieb zu erstellen, die eine Basis von prime Teiler, dann verwenden Sie die in der Schleife zu testen, zahlen für den Primat.
Beim schreiben der Schleife, aber Sie wirklich NICHT wollen, zu uns sqrt(i) in der Schleifenbedingung als ein paar Antworten vorgeschlagen haben.Sie und ich wissen, dass die sqrt ist eine "Reine" Funktion, dass gibt immer die gleiche Antwort, wenn Sie die gleichen Eingabe-parameter.Leider, der compiler weiß NICHT, dass, so dass, wenn Sie etwas wie '<=Math.sqrt(x)' in der Schleife die Bedingung, es werden re-berechnen Sie die Wurzel der Zahl jede iteration der Schleife.
Sie können vermeiden, dass ein paar verschiedene Möglichkeiten.Sie können entweder pre-berechnen Sie die Wurzel vor der Schleife, und verwenden Sie die vorab berechnete Wert in der loop-Zustand, oder Sie können Arbeit in die andere Richtung, und ändern Sie i<Math.sqrt(x) zu i*i<x.Persönlich würde ich pre-Berechnung der Quadratwurzel obwohl-ich glaube, es ist klarer und wahrscheinlich etwas schneller-aber das hängt von der Anzahl der Iterationen der Schleife (die i*i bedeutet, dass es noch immer tun, eine Multiplikation in-the-loop).Mit nur ein paar Iterationen, i*i in der Regel werden schneller.Mit genügend Iterationen, die Verlust von i*i jede iteration überwiegt die Zeit für die Ausführung sqrt einmal außerhalb der Schleife.
Das ist wahrscheinlich ausreichend für die Größe der zahlen, die Sie zu tun -- eine 15-stellige limit bedeutet, dass die Quadratwurzel ist 7 oder 8 Ziffern, die passt in einen ziemlich fairen Betrag von Speicher.Auf der anderen Seite, wenn Sie möchten, um mit zahlen in diesem Bereich eine Menge, möchten Sie vielleicht einen Blick auf einige der anspruchsvolleren prime-checking-algorithmen, wie Pollard oder der Brent-algorithmen.Diese sind komplexer (um es milde auszudrücken), aber eine Menge schneller für große zahlen.
Es gibt andere algorithmen für noch größere zahlen (quadratische Sieb, Allgemeine Nummer Feld Sieb), aber wir nicht in Ihnen, für den Augenblick-Sie sind viel mehr komplexe, und wirklich nur nützlich für den Umgang mit wirklich großen zahlen (GNFS beginnt, um nützlich zu sein in der 100+ - stelligen Bereich).
Erster Schritt: eine Erweiterungsmethode schreiben, um herauszufinden, ob ein Eingang Primzahl
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 Schritt: die Methode schreiben, die alle Primzahlen gedruckt werden, die zwischen 0 und der Anzahl Eingang
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Es kann nur meine Meinung, aber es ist ein weiterer schwerwiegender Fehler in Ihrem Programm (Einstellung die gegebenen ‚Primzahl‘ Frage beiseite, die gründlich beantwortet wurde).
Wie der Rest des Responder, ich gehe davon aus das ist Hausaufgabe, die Sie werden möchten, ein Entwickler zeigt (vermutlich).
Sie müssen lernen, Ihren Code compartmentalize. Es ist nicht etwas, das Sie immer in einem Projekt tun müssen, aber es ist gut zu wissen, wie es zu tun.
Ihre Methode prime_num (long num) könnte einen besseren, beschreibenden Namen steht. Und wenn es soll alle Primzahlen finden weniger als eine bestimmte Anzahl, sollte es sie als Liste zurück. Dies macht es einfacher Ihre Anzeige und Ihre Funktionalität zu trennen.
Wenn es einfach eine IList enthält Primzahlen zurück Sie dann in Ihre Hauptfunktion angezeigt werden könnte (vielleicht eine andere außerhalb Funktion aufrufen sie recht drucken) oder in weiteren Berechnungen auf der ganzen Linie verwenden.
So ist meine beste Empfehlung an Sie ist so etwas wie dies zu tun:
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
Auch wenn Sie irgendwo am Ende arbeiten, wo speration wie dies nicht erforderlich ist, ist es gut zu wissen, wie es zu tun.
Edit_add: Wenn Will Ness ist richtig, dass der Zweck der Frage nur die Ausgabe so lange ein kontinuierlicher Strom von Primzahlen ist wie das Programm ausgeführt wird (durch Drücken Pause / Pause zu unterbrechen und eine beliebige Taste zu starten wieder) ohne ernsthafte Hoffnung auf jeder zu dieser Obergrenze bekommen, dann sollte der Code ohne Obergrenze Argument und eine Bereichsprüfung von „true“ für den ersten ‚i‘ for-Schleife geschrieben werden. Auf der anderen Seite, wenn die Frage der Primzahlen bis zu einer Grenze, dann wird der folgende Code wird den Job viel effizienter mit Verfahrensabteilung nur für ungerade Zahlen, mit dem Vorteil, dass es Speicher nicht überhaupt verwenden, um tatsächlich drucken wollte (es kann auch zu einer Endlosschleife gemäß der oben umgewandelt werden):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
Zunächst erzeugt die Frage Code nicht ausgegeben, weil der, dass seine Schleife Variablen ganze Zahlen sind und die geprüfte Grenze ist ein großes Long-Integer, was bedeutet, dass es unmöglich ist, für die Schleife der Grenze zu erreichen eine innere Schleife Herstellung von Editiert: , wobei die Variable 'j' Schleife zurück herum negative Zahlen; wenn die ‚j‘ Variable auf -1 zurück herum kommt, schlägt die geprüfte Zahl der Prime-Test, da alle Zahlen ohne Rest teilbar sind mit -1 END_EDIT . Auch wenn dies korrigiert wurden, erzeugt die Frage Code sehr langsam ausgegeben, da es bis zu tun 64-Bit-Divisionen von sehr großen Mengen von zusammengesetzten Zahlen (alle geraden Zahlen plus die ungeraden Composites) durch die ganze Reihe von Zahlen bis zu diesem oberen Rand gebunden wird Anzahl von zehn für jede Primzahl des sechzehnten potenziert, dass es möglicherweise produzieren. Der obige Code funktioniert, weil es die Berechnung nur auf den ungeraden Zahlen begrenzt und nur, dass Modulo Divisionen bis zur Quadratwurzel der aktuellen Anzahl getesteten .
Das dauert eine Stunde oder so die Primzahlen zu einer Milliarde bis anzuzeigen, so man die Menge an Zeit, sich vorstellen kann, es zu zehntausend alle Primzahlen zeigen Billionen (10 angehoben bis zum sechzehnten Leistung), zumal die dauern würde, Berechnung wird mit zunehmender Reichweite langsamer. END_EDIT_ADD
Obwohl die Einzeiler (Art) Antwort von @SLaks mit Linq arbeitet, es ist nicht wirklich das Sieb des Eratosthenes, da es nur eine nicht optimierten Version von Testabteilung , nicht optimierte, dass es nicht ungeradees Primzahlen nicht beseitigt, auf dem Platz der gefundenen Basis prime nicht startet, und hört nicht für Culling Basis Primzahlen größer als die Quadratwurzel der oberen Nummer Sieb gegeben. Es ist auch ziemlich langsam aufgrund der mehreren verschachtelten Aufzählung Operationen.
Es ist tatsächlich ein Missbrauch des Verfahrens Linq Aggregate und verwendet nicht effektiv die erste der beiden Linq Bereich des erzeugten. Es kann eine optimierte Verfahrensabteilung mit weniger Aufzählung Kopf wird wie folgt:
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
, die ein Vielfaches schneller läuft als die SLaks beantworten. Allerdings ist es immer noch langsam und speicherintensiv aufgrund der Listengenerierung und die mehreren Aufzählungen sowie die mehrfachen Kluft (impliziert durch die Modulo) Operationen.
Die folgenden Aussagen wahr Sieb des Eratosthenes Umsetzung läuft etwa 30-mal schneller und nimmt viel weniger Speicher, da sie nur eine Ein-Bit-Darstellung pro Anzahl verwendet gesiebt und begrenzt ihre Auszählung der endgültigen Iterator Sequenz Ausgang aufweist sowie die Optimierungen von nur Behandeln odd Komposite, und nur aus den Quadraten der Basis Primzahlen Culling für die Basis der Quadratwurzel der maximalen Zahl Primzahlen, wie folgt:
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
Der obige Code berechnet alle Primzahlen bis zehn Millionen Bereich in etwa 77 Millisekunden auf einem Intel i7-2700K (3,5 GHz).
kann eine der beide statischen Methoden mit den using-Anweisungen und mit der statischen Haupt Methode aufgerufen und geprüft werden, wie folgt:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
, die die Anzahl der Primzahlen in der Folge bis zu der Grenze zeigen, die Last prime gefunden, und die Zeit aufgewendet, die weit in aufzählt.
Edit_add: Um jedoch eine Aufzählung der Anzahl der Primzahlen zu produzieren weniger als zehntausend Billionen (zehn bis sechzehnten Kraft) als die Frage stellt, ein segmentierte ausgelagerten Ansatz Multi-Core Verarbeitung erforderlich ist, sondern auch mit C ++ und dem sehr hoch optimierte PrimeSieve , wäre dies etwas mehr als 400 erfordert Stunden zu produzieren nur die Anzahl der Primzahlen gefunden, und zehn mal so lange sie alle aufzuzählen, so über ein Jahr, was die Frage geht dahin, zu tun. Um es zu tun das nicht optimierten Verfahrensabteilung Algorithmus versucht verwendet, wird es super Äonen und eine sehr sehr lange Zeit auch mit einem optimierten Verfahrensabteilung Algorithmus wie in so etwas wie zehn die zweimillionste Kraft Jahre in Anspruch nehmen (das ist zwei Millionen Nullen Jahre !! !).
Es ist nicht viel Wunder, dass seine Desktop-Rechner saß und ins Stocken geraten, als er versuchte es !!!! Wenn er einen kleineren Bereich, wie eine Million versucht hätte, hätte er noch fand es im Bereich von Sekunden in Anspruch nimmt als umgesetzt.
Die Lösungen, die ich hier posten werden nicht schneiden entweder als auch das letzte Sieb des Eratosthenes wird man etwa 640 Terabyte Speicher für diesen Bereich erforderlich ist.
Aus diesem Grunde nur eine Seite segmentierte Ansatz wie die von PrimeSieve diese Art von Problem für den Bereich verarbeiten kann, wie überhaupt angegeben, und auch das erfordert eine sehr lange Zeit, wie in Wochen bis Jahre, es sei denn man Zugang zu einem hat Super-Computer mit Hunderten von Tausenden von Kernen. END_EDIT_ADD
Riecht nach mehr Hausaufgaben. Meine sehr sehr alte Grafikrechner hatte ein gutes Programm wie dieses ist. Technnically die innere devision Überprüfung Schleife muss nur i ^ (1/2) laufen. Müssen Sie „alle“ Primzahlen zwischen 0 und L finden? Das andere große Problem ist, dass Ihre Schleife Variablen sind „int“, während die Eingangsdaten „long“ ist, wird dies einen Überlauf verursachen machen Loops nicht auch nur einmal auszuführen. Fixieren Sie die Schleife Variablen.
Eine Zeile Code in C #: -
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
Die Sieb des Eratosthenes oben Antwort ist nicht ganz richtig. Wie geschrieben wird es alle Primzahlen zwischen 1 und 1000000 finden Um alle Primzahlen zwischen 1 und num Verwendung zu finden:
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
Der Samen der Aggregate sollte Bereich von 1 bis num sein, da diese Liste die endgültige Liste der Primzahlen enthält. Die Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) ist die Anzahl der Male der Samen gespült wird.
ExchangeCore Foren einen guten haben Konsolenanwendung aufgelistet, die gefunden Primzahlen in eine Datei zu schreiben, sieht, sieht es aus wie Sie auch, dass die gleiche Datei als Ausgangspunkt verwenden können, so dass Sie nicht Primzahlen von 2 neu starten zu finden, und sie bieten einen Download der Datei mit allen gefunden Primzahlen auf 100 Millionen, so wäre es ein guter Anfang sein.
Der Algorithmus auf der Seite nimmt auch ein paar Abkürzungen (ungerade Zahlen und prüft nur auf die Quadratwurzel up), die es extrem effizient macht und es erlaubt Ihnen, lange Zahlen zu berechnen.
so ist dies im Grunde nur zwei Tippfehler ein, die unglücklichste, for (int j = 2; j <= num; j++), die der Grund für die unproduktive Prüfung von 1%2,1%3 ... 1%(10^15-1) ist, die für sehr lange Zeit vergeht so die OP nicht bekommen < em> "jeder Ausgang" . Es sollte stattdessen j < i; worden ist Der ander, kleiner man im Vergleich ist, dass i sollte von 2 starten, nicht von 0:.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Es kann doch nicht zugemutet wird von einem console Druck-out von 28 Billionen Primzahlen oder so in jedem angemessenen Zeitrahmen abgeschlossen werden. So war die ursprüngliche Absicht des Problems offensichtlich einen stetigen Strom von Primzahlen zu drucken, auf unbestimmte Zeit . Deshalb werden alle Lösungen einfache Verwendung von Sieb des Eratosthenes vorschlägt, sind völlig ohne Verdienst hier, weil einfach Sieb des Eratosthenes begrenzt ist - eine Grenze, muss im Voraus eingestellt werden.
Was könnte hier arbeiten, ist die optimierte Probedivision, die die Primzahlen retten würde, wie er sie findet, und Test gegen die Primzahlen, nicht nur alle Zahlen unter den Kandidaten.
Zweite Alternative, mit vielen besseren Komplexität (dh viel schneller) ist ein segmentierte Sieb des Eratosthenes verwenden . Welche ist inkrementell und unbegrenzt.
Beide Systeme verwenden würden double-Inszenierung von Primzahlen : man würde produzieren und die Primzahlen speichern, die von der anderen Stufe in Tests verwendet werden (oder Sieben), weit über die Grenze der erste Stufe (unterhalb seinem quadratischen natürlich - automatisch die erste Stufe erstreckt, als die zweite Stufe weiter gehen würde und weiter oben).
Um ganz ehrlich zu sein, sind einige der vorgeschlagenen Lösungen sehr langsam und sind daher schlecht Vorschläge. Für eine einzelne Zahl zu testen prime sein müssen Sie einige Teilungs / Modulo-Operator, sondern ein Bereich für die Berechnung Sie müssen nicht.
Grundsätzlich Sie nur Zahlen ausschließen, die ein Vielfaches von früher gefundenen Primzahlen sind, wie die (durch Definition) sich nicht Primzahlen.
Ich werde nicht die vollständige Umsetzung geben, so dass zu leicht sein würde, dies ist der Ansatz in Pseudo-Code. (Auf meinem Rechner die tatsächliche Implementierung berechnet alle Primzahlen in einem Sytem.Int32 (2 Miliarden) innerhalb von 8 Sekunden.
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
Die Lösung erfordert ein gutes Verständnis für bitweise Operationen. Aber es Wege und Möglichkeiten, schneller. Sie können auch sicher das Ergebnis des Ergebnisses auf der Disc, wenn Sie sie für den späteren Gebrauch benötigen. Das Ergebnis von 17 * 10 ^ 9 Zahlen können mit 1 GB safed werden, und die Berechnung dieses Ergebnismenge dauert ca. 2 Minuten max.
Ich weiß, die ruhige alte Frage, aber nach dem Lesen hier: Sieb des Eratosthenes Wiki
Dies ist die Art, wie ich es geschrieben hätte, den Algorithmus von Verständnis:
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
In der ersten Schleife füllen wir das Array von booleans mit wahr.
Second for-Schleife beginnt von 2 seit 1 keine Primzahl und prüft, ob Primzahl ist immer noch nicht geändert und dann falsch zuweisen, um den Index j.
letzte Schleife wir nur den Druck, wenn es eine Primzahl ist.
Sehr ähnlich - von einer Übung Sieb des Eratosthenes in C # zu implementieren:
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
Prime Helper sehr schnelle Berechnung
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
U kann das normale Primzahl Konzept muss nur zwei Faktoren (je einen und selbst). So tun wie diese, einfache Möglichkeit,
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
Diese Lösung zeigt alle Primzahlen zwischen 0 und 100.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
Dies ist der schnellste Weg, Primzahlen in C # zu berechnen.
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
Es gibt einige sehr optimale Möglichkeiten, um den Algorithmus zu implementieren. Aber wenn Sie nicht wissen viel über Mathematik und Sie einfach die Definition von vorrangiger als die Anforderung wie folgt vor: eine Zahl, die nur teilbar durch 1 und durch sich selbst (und sonst nichts), hier ist ein einfach zu verstehen Code für positive Zahlen.
istpublic bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
Da jede Zahl von 1 und durch sich selbst teilbar ist, beginnen wir von 2 ab, bis die Zahl unmittelbar vor selbst zu überprüfen. Das ist die grundlegende Argumentation.
Sie können dies auch:
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
