Der effizienteste Code für die ersten 10000 Primzahlen?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich möchte die ersten 10000 Primzahlen drucken.Kann mir jemand den effizientesten Code dafür geben?Erläuterungen:
- Es spielt keine Rolle, ob Ihr Code für n > 10000 ineffizient ist.
- Die Größe des Codes spielt keine Rolle.
- Sie können die Werte nicht einfach auf irgendeine Weise fest codieren.
Lösung
Das Sieb von Atkin ist wahrscheinlich das, wonach Sie suchen. Die obere Laufzeitgrenze beträgt O(N/log log N).
Wenn Sie nur die Zahlen um 1 mehr und 1 weniger als die Vielfachen von 6 berechnen, könnte es sogar noch schneller gehen, da alle Primzahlen über 3 um 1 von einem Vielfachen von sechs entfernt sind.Quelle für meine Aussage
Andere Tipps
Ich empfehle ein Sieb, entweder das Sieb des Eratosthenes oder der Sieb von Atkin.
Das Sieb oder Eratosthenes ist wahrscheinlich die intuitivste Methode, eine Liste von Primzahlen zu finden.Grundsätzlich gilt:
- Schreiben Sie eine Liste mit Zahlen von 2 bis zur gewünschten Grenze auf, sagen wir 1000.
- Nehmen Sie die erste Zahl, die nicht durchgestrichen ist (für die erste Iteration ist dies 2) und streichen Sie alle Vielfachen dieser Zahl aus der Liste.
- Wiederholen Sie Schritt 2, bis Sie das Ende der Liste erreicht haben.Alle nicht durchgestrichenen Zahlen sind Primzahlen.
Natürlich gibt es einige Optimierungen, die vorgenommen werden können, um diesen Algorithmus schneller arbeiten zu lassen, aber das ist die Grundidee.
Das Sieb von Atkin verwendet einen ähnlichen Ansatz, aber leider weiß ich nicht genug darüber, um es Ihnen zu erklären.Aber ich weiß, dass der Algorithmus, den ich verlinkt habe, 8 Sekunden braucht, um alle Primzahlen bis zu 1000000000 auf einem alten Pentium II-350 herauszufinden
Sieb des Eratosthenes Quellcode: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Sieve of Atkin Quellcode: http://cr.yp.to/primegen.html
Dies verstößt zwar nicht strikt gegen die Hardcoding-Beschränkung, kommt aber sehr nahe.Warum laden Sie diese Liste nicht stattdessen programmgesteuert herunter und drucken sie aus?
GateKiller, wie wäre es mit dem Hinzufügen von a break dazu if im foreach Schleife?Das würde die Sache beschleunigen eine Menge Denn wenn 6 durch 2 teilbar ist, müssen Sie nicht mit 3 und 5 prüfen.(Ich würde Ihre Lösung sowieso positiv bewerten, wenn ich genug Reputation hätte :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
In Haskell können wir die mathematische Definition des Siebes des Eratosthenes fast wörtlich niederschreiben: „Primzahlen sind natürliche Zahlen über 1 ohne zusammengesetzte Zahlen, wobei zusammengesetzte Zahlen durch Aufzählung der Vielfachen jeder Primzahl gefunden werden":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 ist nahezu augenblicklich.
Verweise:
Der obige Code lässt sich leicht so anpassen, dass er nur mit Quoten arbeitet. primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).Die Zeitkomplexität ist deutlich verbessert (auf knapp eins). Protokoll Faktor über dem Optimalwert) durch Falten in einer baumartigen Struktur, und die Raumkomplexität beträgt drastisch verbessert von Mehrstufige Primzahlenproduktion, In
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(In Haskell werden die Klammern zur Gruppierung verwendet, ein Funktionsaufruf wird nur durch Nebeneinanderstellung gekennzeichnet, (:) ist ein Nachteile Operator für Listen und (.) ist ein funktionaler Kompositionsoperator: (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt:log(log(10000)) ist ~2
Aus dem Wikipedia-Artikel (den Sie zitiert haben) Sieb von Atkin:
Dieses Sieb berechnet Primes bis n mit n
O(N/log log N)Operationen mit nur n1/2+o(1) Erinnerungsstücke.Das ist ein bisschen besser als das Sieb von Eratosthenes, der verwendetO(N)Operationen und O(N1/2(log log l)/log n) Speicherbits (A.O.L.Atkin, D.J.Bernstein, 2004).Diese asymptotischen rechnerischen Komplexitäten umfassen einfache Optimierungen wie Radfaktorisierung und Aufteilung der Berechnung auf kleinere Blöcke.
Angesichts der asymptotischen Rechenkomplexität entlang O(N) (für Eratosthenes) und O(N/log(log(N))) (für Atkin) können wir nicht sagen (für klein). N=10_000), welcher Algorithmus, wenn er implementiert wird, schneller ist.
Achim Flammenkamp schrieb ein Das Sieb des Eratosthenes:
zitiert von:
@num1
In Intervallen, die um 10^9 größer sind, wird das Sieb von Eratosthenen sicherlich durch das Sieb von Atkins und Bernstein übertrifft, der irreduzibäre binäre quadratische Formen verwendet.In ihrem Papier finden Sie Hintergrundinformationen sowie Absatz 5 von W.Galways Ph.D.These.
Deshalb für 10_000 Das Sieb des Eratosthenes kann schneller sein als das Sieb des Atkin.
Um OP zu beantworten, lautet der Code prime_sieve.c (zitiert von num1)
Mit GMP könnte man Folgendes schreiben:
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
Auf meinem 2,33 GHz MacBook Pro läuft es wie folgt ab:
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Berechnung von 1.000.000 Primzahlen auf demselben Laptop:
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP ist für solche Dinge stark optimiert.Sofern Sie die Algorithmen nicht wirklich verstehen möchten, indem Sie Ihre eigenen schreiben, empfehlen wir Ihnen, libGMP unter C zu verwenden.
Überhaupt nicht effizient, aber Sie können einen regulären Ausdruck verwenden, um auf Primzahlen zu testen.
/^1?$|^(11+?)\1+$/
Dies testet, ob für eine Zeichenfolge bestehend aus k “1"S, k Ist nicht prim (d. h.ob die Zeichenfolge aus einem besteht „1” oder eine beliebige Anzahl von „1”s, das als ausgedrückt werden kann N-äres Produkt).
Ich habe den gefundenen Code angepasst CodeProjekt um Folgendes zu erstellen:
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
Beim Testen auf meinem ASP.NET-Server dauerte die Ausführung der Routine etwa eine Minute.
Hier ist ein Sieb des Eratosthenes, das ich vor ein paar Tagen in PowerShell geschrieben habe.Es verfügt über einen Parameter zum Identifizieren der Anzahl der Primzahlen, die zurückgegeben werden sollen.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
Sieb des Eratosthenes ist aufgrund seiner Einfachheit und Geschwindigkeit der richtige Weg.Meine Implementierung in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
CPU-Zeit zum Finden von Primzahlen (auf Pentium Dual Core E2140 1,6 GHz, mit Einzelkern)
~ 4s für lim = 100.000.000
Anpassen und Weiterverfolgen GateKiller, hier ist die endgültige Version, die ich verwendet habe.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
Im Grunde ist es dasselbe, aber ich habe den Vorschlag „Break on Sqrt“ hinzugefügt und einige der Variablen geändert, damit es besser zu mir passt.(Ich habe an Euler gearbeitet und brauchte die 10001. Primzahl)
Das Sieb scheint die falsche Antwort zu sein.Das Sieb liefert die Primzahlen bis zu eine Zahl N, nicht der erst ein Primzahlen.Führen Sie @Imran oder @Andrew Szeto aus, und Sie erhalten die Primzahlen bis N.
Das Sieb könnte immer noch verwendbar sein, wenn Sie immer wieder Siebe für immer größere Zahlen ausprobieren, bis Sie eine bestimmte Größe Ihrer Ergebnismenge erreicht haben, und die bereits erhaltenen Zahlen etwas zwischenspeichern, aber ich glaube, es wäre immer noch nicht schneller als eine Lösung wie die von @Pat .
In Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Der Deque-Sieb-Algorithmus, erwähnt von BenGoldberg verdient eine genauere Betrachtung, nicht nur weil es sehr elegant ist, sondern auch weil es gelegentlich in der Praxis nützlich sein kann (im Gegensatz zum Sieve of Atkin, das eine rein akademische Übung ist).
Die Grundidee des Deque-Sieve-Algorithmus besteht darin, ein kleines, verschiebbares Sieb zu verwenden, das nur groß genug ist, um mindestens ein separates Vielfaches für jeden der aktuell „aktiven“ Primfaktoren zu enthalten – d. h.diejenigen Primzahlen, deren Quadrat die niedrigste Zahl, die derzeit vom beweglichen Sieb dargestellt wird, nicht überschreitet.Ein weiterer Unterschied zum SoE besteht darin, dass das Deque-Sieb die tatsächlichen Faktoren in den Slots von Verbundwerkstoffen und nicht in Booleschen Werten speichert.
Der Algorithmus erweitert die Größe des Siebfensters nach Bedarf, was zu einer ziemlich gleichmäßigen Leistung über einen weiten Bereich führt, bis das Sieb beginnt, die Kapazität des L1-Cache der CPU merklich zu überschreiten.Die letzte Primzahl, die vollständig passt, ist 25.237.523 (die 1.579.791. Primzahl), was einen ungefähren Richtwert für den angemessenen Betriebsbereich des Algorithmus ergibt.
Der Algorithmus ist ziemlich einfach und robust und weist über einen viel größeren Bereich eine gleichmäßige Leistung auf als ein unsegmentiertes Eratosthenes-Sieb.Letzteres ist um einiges schneller, solange sein Sieb vollständig in den Cache passt, d.h.bis zu 2^16 für ein Nur-Quoten-Sieb mit Byte-großen Bools.Dann lässt die Leistung immer mehr nach, bleibt aber trotz des Handicaps immer deutlich schneller als die Deque (zumindest in kompilierten Sprachen wie C/C++, Pascal oder Java/C#).
Hier ist eine Wiedergabe des Deque-Sieve-Algorithmus in C#, weil ich finde, dass diese Sprache – trotz ihrer vielen Mängel – viel praktischer für das Prototyping von Algorithmen und Experimente ist als das äußerst umständliche und pedantische C++. (Randnotiz:Ich benutze das kostenlose LINQPad Dadurch ist es möglich, direkt einzutauchen, ohne die ganze Unordnung beim Einrichten von Projekten, Makefiles, Verzeichnissen oder so weiter, und es bietet mir den gleichen Grad an Interaktivität wie eine Python-Eingabeaufforderung.
C# hat keinen expliziten Deque-Typ, sondern den Plain-Typ List<int> Funktioniert gut genug, um den Algorithmus zu demonstrieren.
Notiz:Diese Version verwendet kein Deque für die Primzahlen, da es einfach keinen Sinn macht, sqrt(n) aus n Primzahlen herauszuschneiden.Was würde es nützen, 100 Primzahlen zu entfernen und 9900 übrig zu lassen?Zumindest werden auf diese Weise alle Primzahlen in einem übersichtlichen Vektor gesammelt und stehen für die weitere Verarbeitung bereit.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
Hier sind die beiden Hilfsfunktionen:
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
Der wahrscheinlich einfachste Weg, den Algorithmus zu verstehen, besteht darin, ihn sich als ein spezielles segmentiertes Sieb von Eratosthenes mit einer Segmentgröße von 1 vorzustellen, begleitet von einem Überlaufbereich, in dem die Primzahlen zur Ruhe kommen, wenn sie über das Ende des Segments schießen.Außer dass die einzelne Zelle des Segments (auch bekannt als sieve[0]) ist bereits gesiebt, als wir dort ankommen, weil es überfahren wurde, während es Teil des Überlaufbereichs war.
Die Zahl, die dargestellt wird durch sieve[0] wird festgehalten sieve_base, Obwohl sieve_front oder window_base Wäre auch ein guter Name, der es ermöglicht, Parallelen zu Bens Code oder Implementierungen segmentierter/fensterförmiger Siebe zu ziehen.
Wenn sieve[0] einen Wert ungleich Null enthält, dann ist dieser Wert ein Faktor von sieve_base, die somit als zusammengesetzt erkannt werden kann.Da Zelle 0 ein Vielfaches dieses Faktors ist, lässt sich der nächste Hop leicht berechnen, der einfach 0 plus diesem Faktor ist.Sollte diese Zelle bereits von einem anderen Faktor belegt sein, addieren wir einfach den Faktor erneut und so weiter, bis wir ein Vielfaches des Faktors finden, in dem derzeit kein anderer Faktor geparkt ist (bei Bedarf erweitern wir das Sieb).Dies bedeutet auch, dass es nicht erforderlich ist, die aktuellen Arbeitsversätze der verschiedenen Primzahlen von einem Segment zum nächsten zu speichern, wie bei einem normalen segmentierten Sieb.Wann immer wir einen Faktor finden sieve[0], sein aktueller Arbeitsoffset ist 0.
Die aktuelle Primzahl kommt auf folgende Weise ins Spiel.Eine Primzahl kann erst dann aktuell werden, wenn sie im Strom vorkommt (d. h.wenn es als Primzahl erkannt wurde, weil es nicht mit einem Faktor markiert ist), und es bleibt bis genau zu dem Zeitpunkt aktuell, an dem es passiert sieve[0] erreicht seinen Platz.Alle unteren Vielfachen dieser Primzahl müssen aufgrund der Aktivitäten kleinerer Primzahlen gestrichen worden sein, genau wie in einem normalen SoE.Aber keine der kleineren Primzahlen kann das Quadrat streichen, da der einzige Faktor des Quadrats die Primzahl selbst ist und zu diesem Zeitpunkt noch nicht im Umlauf ist.Das erklärt die Maßnahmen, die der Algorithmus in diesem Fall ergriffen hat sieve_base == current_prime_squared (was impliziert sieve[0] == 0, Übrigens).
Jetzt ist der Fall sieve[0] == 0 && sieve_base < current_prime_squared ist leicht erklärt:es bedeutet das sieve_base darf kein Vielfaches einer Primzahl sein, die kleiner als die aktuelle Primzahl ist, sonst wäre sie als zusammengesetzt markiert worden.Ich kann auch kein höheres Vielfaches der aktuellen Primzahl sein, da ihr Wert kleiner als das Quadrat der aktuellen Primzahl ist.Daher muss es eine neue Primzahl sein.
Der Algorithmus ist offensichtlich vom Sieb des Eratosthenes inspiriert, aber ebenso offensichtlich ist er sehr unterschiedlich.Das Sieb des Eratosthenes verdankt seine überlegene Geschwindigkeit der Einfachheit seiner elementaren Operationen:Eine einzige Indexaddition und ein Speichervorgang für jeden Schritt der Operation ist alles, was über einen längeren Zeitraum hinweg ausgeführt wird.
Hier ist ein einfaches, unsegmentiertes Eratosthenes-Sieb, das ich normalerweise zum Sieben von Faktorprimzahlen im ushort-Bereich verwende, d. h.bis zu 2^16.Für diesen Beitrag habe ich es durch Ersetzen so geändert, dass es über 2^16 hinaus funktioniert int für ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
Beim Sieben der ersten 10.000 Primzahlen wird ein typischer L1-Cache von 32 KiByte überschritten, aber die Funktion ist immer noch sehr schnell (Bruchteile einer Millisekunde selbst in C#).
Wenn Sie diesen Code mit dem Deque-Sieb vergleichen, ist es leicht zu erkennen, dass die Operationen des Deque-Sieb viel komplizierter sind und es seinen Mehraufwand nicht effektiv amortisieren kann, da es immer die kürzestmögliche Strecke von Kreuzungen hintereinander durchführt (genau ein einziges Ankreuzen, nachdem alle bereits angekreuzten Vielfachen übersprungen wurden).
Notiz:der C#-Code verwendet int anstatt uint weil neuere Compiler die Angewohnheit haben, minderwertigen Code zu generieren uint, wahrscheinlich um die Leute zu vorzeichenbehafteten Ganzzahlen zu bewegen ...In der C++-Version habe ich den obigen Code verwendet unsigned durchgehend, natürlich;Der Benchmark musste in C++ sein, weil ich wollte, dass er auf einem vermeintlich adäquaten Deque-Typ basiert (std::deque<unsigned>;Es gab keinen Leistungsgewinn durch die Verwendung unsigned short).Hier sind die Zahlen für meinen Haswell-Laptop (VC++ 2015/x64):
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
Notiz:Die C#-Zeiten sind ziemlich genau doppelt so hoch wie die C++-Zeiten, was für C# ziemlich gut ist und das zeigt List<int> ist kein Trottel, auch wenn er als Deque missbraucht wird.
Der einfache Sieve-Code sprengt immer noch die Deque, obwohl er bereits außerhalb seines normalen Arbeitsbereichs arbeitet (L1-Cache-Größe um 50 % überschritten, mit entsprechender Cache-Überlastung).Der dominierende Teil ist hier das Auslesen der gesiebten Primzahlen und wird durch das Cache-Problem nicht wesentlich beeinflusst.In jedem Fall wurde die Funktion zum Sieben der Faktoren von Faktoren entwickelt, d. h.Ebene 0 in einer 3-Ebenen-Siebhierarchie und muss normalerweise nur einige hundert Faktoren oder eine geringe Anzahl von Tausenden zurückgeben.Daher seine Einfachheit.
Die Leistung könnte um mehr als eine Größenordnung verbessert werden, indem ein segmentiertes Sieb verwendet und der Code zum Extrahieren der gesiebten Primzahlen optimiert wird (Mod 3 abgestuft und zweimal abgerollt, oder Mod 15 und einmal abgerollt), und es könnte noch mehr Leistung herausgeholt werden den Code mithilfe eines Mod 16- oder Mod 30-Rads mit allem Drum und Dran (d. h.vollständiges Abrollen für alle Rückstände).So etwas wird in meiner Antwort auf erklärt Finden Sie eine Primzahl in der Primzahl bei Code Review, wo ein ähnliches Problem besprochen wurde.Aber es ist schwer zu erkennen, welchen Sinn es hat, bei einer einmaligen Aufgabe die Zeit unter einer Millisekunde zu verbessern ...
Um die Sache ein wenig ins rechte Licht zu rücken, hier die C++-Timings für die Siebung von bis zu 100.000.000:
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
Im Gegensatz dazu erledigt ein segmentiertes Sieb in C# mit ein paar Schnickschnack die gleiche Aufgabe in 95 ms (keine C++-Timings verfügbar, da ich Code-Herausforderungen derzeit nur in C# durchführe).
In einer interpretierten Sprache wie Python, in der jede Operation mit hohen Kosten verbunden ist und der Overhead des Interpreters alle Unterschiede aufgrund von vorhergesagten vs.falsch vorhergesagte Verzweigungen oder Unterzyklusoperationen (Verschiebung, Addition) vs.Mehrzyklusoperationen (Multiplikation und vielleicht sogar Division).Dadurch wird der Einfachheitsvorteil des Siebes des Eratosthenes zwangsläufig untergraben, und dies könnte die Deque-Lösung etwas attraktiver machen.
Außerdem werden viele der von anderen Befragten in diesem Thema gemeldeten Zeitangaben wahrscheinlich von dominiert Ausgabezeit.Das ist ein völlig anderer Krieg, in dem meine Hauptwaffe eine einfache Klasse wie diese ist:
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
Das Schreiben von 10.000 (sortierten) Zahlen dauert weniger als 1 ms.Es handelt sich um eine statische Klasse, da sie für die Einbindung von Text in Einreichungen von Codierungsherausforderungen mit minimalem Aufwand und ohne Overhead gedacht ist.
Im Allgemeinen fand ich es so viel schneller, wenn gezielt an ganzen Chargen gearbeitet wird, also ein bestimmter Bereich gesiebt wird, dann alle Primzahlen in einen Vektor/ein Array extrahiert werden, dann das gesamte Array gesprengt wird, dann der nächste Bereich gesiebt wird und so weiter, anstatt alles miteinander zu vermischen.Die getrennten Funktionen, die sich auf bestimmte Aufgaben konzentrieren, erleichtern auch die Kombination, ermöglichen die Wiederverwendung und erleichtern die Entwicklung/Tests.
Hier ist mein VB 2008-Code, der alle Primzahlen <10.000.000 in 1 Minute und 27 Sekunden auf meinem Arbeitslaptop findet.Es überspringt gerade Zahlen und sucht nur nach Primzahlen, die < dem Quadratwert der Testzahl sind.Es dient nur dazu, Primzahlen von 0 bis zu einem Endwert zu finden.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Der folgende Mathcad-Code berechnete die ersten Millionen Primzahlen in weniger als 3 Minuten.
Bedenken Sie, dass dies für alle Zahlen Gleitkomma-Doubles verwenden würde und grundsätzlich interpretiert wird.Ich hoffe, die Syntax ist klar.
Hier ist eine C++-Lösung, die eine Form von SoE verwendet:
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
Beachten Sie, dass diese Version des Siebs unbegrenzt Primzahlen berechnen kann.
Beachten Sie auch die STL deque dauert O(1) Zeit zum Auftritt push_back, pop_front, und Direktzugriff durch Subskription.
Der resize Die Operation dauert O(n) Zeit, wo n ist die Anzahl der hinzugefügten Elemente.Aufgrund der Art und Weise, wie wir diese Funktion verwenden, können wir sie als kleine Konstante behandeln.
Der Körper des while einhängen my_insert wird ausgeführt O(log log n) mal, wo n entspricht der Variablen maybe_prime.Dies liegt daran, dass der Bedingungsausdruck des while wird für jeden Primfaktor von einmal als wahr ausgewertet maybe_prime.Sehen "Teilerfunktion" auf Wikipedia.
Mit der Anzahl multiplizieren my_insert heißt, zeigt, dass es dauern sollte O(n log log n) Zeit zum Auflisten n Primzahlen...Das ist, wenig überraschend, die zeitliche Komplexität, die das Sieb des Eratosthenes haben soll.
Allerdings während dieser Code Ist effizient, das ist es nicht am effizientesten...Ich würde dringend empfehlen, eine spezielle Bibliothek für die Generierung von Primzahlen zu verwenden, z Ursieb.Jede wirklich effiziente, gut optimierte Lösung benötigt mehr Code, als irgendjemand in Stackoverflow eingeben möchte.
Mit „Sieve of Eratosthenes“ ist die Berechnung im Vergleich zum „bekannten“ Primzahlenalgorithmus deutlich schneller.
Durch die Verwendung von Pseudocode aus dem Wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), kann ich die Lösung auf C# haben.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes(100000000) dauert 2 s und 330 ms.
NOTIZ:Der Wert kann je nach Hardwarespezifikationen variieren.
Ich verbringe einige Zeit damit, ein Programm zu schreiben, das viele Primzahlen berechnet, und das ist der Code, den ich verwende, um eine Textdatei zu berechnen, die die ersten 1.000.000.000 Primzahlen enthält.Es ist auf Deutsch, aber das Interessante ist die Methode calcPrimes().Die Primzahlen werden in einem Array namens Primzahlen gespeichert.Ich empfehle eine 64-Bit-CPU, da die Berechnungen mit 64-Bit-Ganzzahlen erfolgen.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
Ich habe dies mit Python geschrieben, da ich gerade angefangen habe, es zu lernen, und es funktioniert einwandfrei.Die 10.000ste Primzahl wird mit diesem Code wie in beschrieben generiert http://primes.utm.edu/lists/small/10000.txt.Um zu überprüfen, ob n prim ist oder nicht, dividiere n durch die Zahlen von 2 Zu sqrt(n).Wenn einer dieser Zahlenbereiche perfekt teilbar ist n dann ist es nicht prim.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Ich arbeite seit etwa einem Jahr daran, Primzahlen zu finden.Folgendes fand ich am schnellsten:
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 Nanosekunden, um zu 2147483629 zu gelangen, beginnend bei 2.
Hier ist mein Code, der die ersten 10.000 Primzahlen in 0,049655 Sekunden auf meinem Laptop, erste 1.000.000 Primzahlen in weniger als 6 Sekunden und die ersten 2.000.000 in 15 Sekunden findet
Eine kleine Erklärung.Diese Methode verwendet zwei Techniken, um Primzahlen zu finden
- Erstens setzt sich jede Nicht-Primzahl aus Vielfachen von Primzahlen zusammen. Bei diesem Codetest wird die Testzahl durch kleinere Primzahlen anstelle einer beliebigen Zahl geteilt. Dies verringert die Berechnung für eine 4-stellige Zahl um mindestens das Zehnfache und sogar noch mehr eine größere Zahl
- Zweitens wird neben der Division durch Primzahlen nur durch Primzahlen dividiert, die kleiner oder gleich der Wurzel der zu testenden Zahl sind, was die Berechnungen weiter reduziert. Dies funktioniert, weil jede Zahl, die größer als die Wurzel der Zahl ist, eine entsprechende Gegenzahl hat muss kleiner als die Wurzel der Zahl sein, aber da wir bereits alle Zahlen getestet haben, die kleiner als die Wurzel sind, müssen wir uns nicht mit Zahlen herumschlagen, die größer als die Wurzel der zu testenden Zahl sind.
Beispielausgabe für die ersten 10.000 Primzahlen
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Hier ist der Code in C -Sprache, geben Sie 1 und dann 10.000 ein, um die ersten 10.000 Primzahlen auszudrucken.
Bearbeiten:Ich habe vergessen, dass dies eine Mathematikbibliothek enthält. Wenn Sie Windows oder Visual Studio verwenden, sollte das in Ordnung sein, aber unter Linux müssen Sie den Code mit dem Argument -lm kompilieren, sonst funktioniert der Code möglicherweise nicht
Beispiel:gcc -Wall -o "%e" "%f" -lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
Hier der Code, den ich gemacht habe:
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
Verwendung der Methode Array.prototype.find() in Javascript.2214,486 ms
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
Ich kann dir ein paar Tipps geben, du musst es umsetzen.
- Erhalten Sie für jede Zahl die Hälfte dieser Zahl.Z.B.Um 21 zu prüfen, erhalten Sie den Rest nur durch Division aus dem Bereich 2-10.
- Wenn es eine ungerade Zahl ist, dividieren Sie nur durch eine ungerade Zahl und umgekehrt.Teilen Sie beispielsweise für 21 nur durch 3, 5, 7, 9.
Die effizienteste Methode, die ich bisher ausprobiert habe.
Da Sie nur erst 10000 Primzahlen wollen, anstatt den komplexen Algorithmus zu kodieren, werde ich Folgendes vorschlagen
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
Jetzt ist der Anruf so wichtig, wie Sie ihn brauchen
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
