Ich habe versucht, ein Problem mit SPOJ zu lösen. Wir müssen das n-te Zwillings-Primzahlpaar berechnen (die Primzahlen unterscheiden sich um 2). n kann so groß wie 10 ^ 5 sein. Ich versuchte eine Vorberechnung mit einem Sieb, ich musste bis 10 ^ 8 sieben, um das Maximum n Zwillingsprime zu erhalten, aber das Zeitlimit ist streng (2s) und es überschreitet Zeit. Ich bemerkte, dass Leute es in 0.00 Sekunden gelöst haben, also suchte ich nach einer Formel auf Google, und konnte nichts hilfreiches bekommen. Könnte jemand mich bitte führen?
Vielen Dank im Voraus !!
Laut Wolfram Alpha reicht das Sieben bis zu 20.000.000. Benutze das einfache Sieb von Eratosthenes, mit Quoten, mit vector<bool> in C ++ (in welcher Sprache hast du BTW benutzt?).
Verfolgen Sie die Zwillings-Primzahlen direkt in der Siebschleife. Bewahre die untere Primzahl eines Paares in einem separaten Vektor auf, wenn du die Zwillinge findest, und wenn ein Index außerhalb der Reihenfolge (kleiner als vorher) angefordert wird (und das sind, im Gegensatz zu den Beispielen auf der Beschreibungsseite), gerade Holen Sie sich die Prime aus diesem Speicher:
%Vor%usw. Got accept mit 1,05 sec (0,18 sec auf Ideone). Oder entwirren Sie die Logik - berechnen Sie einfach 100.000 Twin-Prime-Paare sofort und greifen Sie danach in einer separaten Schleife darauf zu (0.94 Sek.).
Aus Neugierde habe ich das Problem mit zwei Varianten eines Sievers von Eratosthenes gelöst. Die erste Variante wurde auf der Prüfmaschine in 0,93 Sekunden und die zweite in 0,24 Sekunden abgeschlossen. Zum Vergleich, auf meinem Computer, der erste in 0,08s und der zweite in 0,04s fertig.
Das erste war ein Standard-Sieb auf den ungeraden Zahlen, das zweite ein etwas ausgefeilteres Sieb, das zusätzlich zu den geraden Zahlen auch die Vielfachen von 3 weglässt.
Die Testmaschinen von SPOJ sind alt und langsam, daher läuft ein Programm viel länger auf ihnen als auf einer typischen neuen Box; und sie haben kleine Caches, deshalb ist es wichtig, die Berechnung klein zu halten.
Damit ist ein Sieb von Eratosthenes schnell genug. Es ist jedoch sehr wichtig, die Speichernutzung gering zu halten. Die erste Variante, die ein Byte pro Nummer verwendet, gab "Zeitlimit überschritten" auf SPOJ, lief aber in 0,12s auf meiner Box. Angesichts der Eigenschaften der SPOJ-Testmaschinen verwenden Sie ein Bit-Sieb , um es in der vorgegebenen Zeit zu lösen.
Auf der SPOJ-Maschine habe ich eine deutliche Beschleunigung (Laufzeit 0,14s) bekommen, indem ich den Platz des Siebes weiter halbiert habe. Da - abgesehen von dem ersten Paar (3,5) - alle Primzahlzwillinge die Form (6*k-1, 6*k+1) haben, und du nicht wissen musst, welche der beiden Zahlen zusammengesetzt ist, wenn k kein Zwillingsprimepaar ergibt, es genügt, nur die Indizes k zu durchforsten.
( 6*k + 1 ist genau dann durch 5 teilbar, wenn k = 5*m + 4 für einige m und 6*k - 1 genau dann durch 5 teilbar ist, wenn k = 5*m+1 für einige m , also 5 abmarkieren würde 5*m ± 1, m >= 1 führt nicht zu Primzahlzwillingen.In ähnlicher Weise ist 6*k+1 genau dann durch 13 teilbar, wenn k = 13*m + 2 für einige m und 6*k - 1 genau dann, wenn k = 13*m - 2 für einige m , also 13 würde 13*m ± 2 abmarkieren.)
Dies ändert nicht die Anzahl der Markierungen, so dass bei einem ausreichend großen Cache die Laufzeitänderung gering ist, aber bei kleinen Caches ist dies eine erhebliche Beschleunigung.
Noch eine Sache. Ihr Limit von 10 8 ist viel zu hoch. Ich habe eine untere Grenze (20 Millionen) verwendet, die das 100.000 th Zwillings-Primzahl-Paar nicht um so viel überschätzt. Mit einer Grenze von 10 <8> wäre die erste Variante sicherlich nicht rechtzeitig fertig geworden, die zweite wahrscheinlich nicht.
Mit dem reduzierten Limit muss ein Sieve of Atkin etwas optimiert werden, um die Eratosthenes-Variante zu übertreffen, die gerade Zahlen und Vielfache von 3 auslässt. Eine naive Implementierung wird deutlich langsamer sein.
Einige Bemerkungen zu Ihrem (Wikipedia Pseudocode) Atkin Sieb:
%Vor%Sie brauchen das zweite Array nicht, der größere Partner eines Prime-Twin-Paars kann leicht aus dem kleineren berechnet werden. Sie verschwenden Speicherplatz und zerstören den Cache-Lokalisierungswert von zwei Arrays. (Das ist jedoch geringfügig im Vergleich zu der Zeit, die für das Sieben benötigt wird.)
%Vor%Das ist heutzutage bei vielen Betriebssystemen ein sofortiger Segfault, selbst bei einem reduzierten Limit. Die Stapelgröße ist oft auf 8 MB oder weniger begrenzt. Arrays dieser Größe sollten auf dem Heap zugeordnet werden.
Wie oben erwähnt, macht die Verwendung von bool pro Zahl das Programm viel langsamer als nötig. Sie sollten ein std::bitset oder std::vector<bool> verwenden oder die Bits selbst mischen. Es ist auch ratsam, mindestens die geraden Zahlen wegzulassen.
Das ist furchtbar ineffizient. Es versucht viel zu viele x-y-Kombinationen, für jede Kombination macht es drei oder vier Divisionen, um den Rest modulo 12 zu überprüfen und es springt im Array hin und her.
Trennen Sie die verschiedenen Quadrate.
Für 4*x^2 + y^2 ist es offensichtlich, dass Sie nur x < sqrt(limit)/2 und ungerade y berücksichtigen müssen. Dann ist der Rest modulo 12 1, 5 oder 9. Wenn der Rest 9 ist, dann ist 4*x^2 + y^2 tatsächlich ein Vielfaches von 9, also würde eine solche Zahl als nicht quadratisch frei eliminiert werden. Es ist jedoch vorzuziehen, die Vielfachen von 3 aus dem Sieb ganz wegzulassen und die Fälle n % 12 == 1 und n % 12 == 5 getrennt zu behandeln.
Für 3*x^2 + y^2 ist es offensichtlich, dass Sie nur x < sqrt(limit/3) berücksichtigen müssen und ein wenig Nachdenken zeigt, dass x ungerade und y gerade (und nicht durch 3 teilbar) sein müssen.
Für 3*x^2 - y^2 mit y < x ist es offensichtlich, dass Sie nur y < sqrt(limit/2) berücksichtigen müssen. Betrachtet man die Reste modulo 12, sieht man, dass y nicht durch 3 teilbar sein darf und x und y unterschiedliche Parität haben müssen.
Ich habe AC in 0.66s. Da es Lösungen mit 0.0s gibt, nehme ich an, dass bessere Optimierungen möglich sind, jedoch beschreibe ich meinen Ansatz hier.
Ich habe eine grundlegende Optimierung in Sieve of Eratosthenes verwendet. Sie wissen, dass 2 die einzige gerade Primzahl ist, mit der Sie Ihre Rechenzeit und Speicher für die Berechnung von Primzahlen um die Hälfte reduzieren können.
Zweitens sind alle Zahlen, die Primzahlzwillinge sind, keine Vielfachen von 2 und 3 (wie sie Primzahlen sind!). Also, diese Zahlen werden in der Form 6N+1 und 6N+5 sein (Rest wird sicher nicht Primzahlen sein). %Code%. Es ist also ersichtlich, dass 6N+5 = 6N+6-1 = 6(N+1)-1 und 6N+1 möglicherweise Primzahlzwillinge für 6N-1 & gt; = 1 sind. Sie berechnen also alle diese Werte mit den zuvor berechneten Primzahlen. (Trivialfall ist 3 5)
Hinweis: Sie müssen keine Primzahlen bis 10 ^ 8 berechnen, die obere Grenze ist viel niedriger. [Bearbeiten: Ich kann meinen Code teilen, wenn Sie möchten, aber es wäre besser, wenn Sie selbst eine Lösung finden. :)]
Eine Beschreibung eines effizienten Algorithmus, um dies zu lösen, finden Sie hier @ Programmierung Praxis Eintrag Außerdem werden Schema und Perl-Beispielcode bereitgestellt.
Ich berechnete eine große Liste von Primzahlen unter Verwendung des Siebs von Eratosthenes vor und durchblätterte dann die Liste, indem ich Gegenstände zählte, die 2 weniger als ihr Nachfolger waren, bis ich n von ihnen fand. Läuft in 1.42 Sekunden bei Ссылка . Ich würde auch gerne wissen, wie man die Antwort in null Sekunden berechnet.
%Vor%Hier ist eine Prozedur, die Ihre Frage beantworten könnte:
Primzahlen, die, wenn sie durch 3 geteilt werden, gleiche Quotienten haben, wenn sie auf dezimal 0 (null) korrigiert werden, sind Twin Primes.
Dies kann als
geschrieben werdenFür jedes Primzahlpaar Px, Py, wenn [Px / 3, 0] = [Py / 3, 0], dann sind Px und Py Primzahlzwillinge.
Die Grundlage dafür ist, dass, wenn sich Primzahlen um 2 unterscheiden, die Division aller Primzahlen von Interesse eindeutige Quotienten ergibt, wenn die Quotienten auf Dezimal Null korrigiert werden. Primzahlen, die nicht durch 2 getrennt sind, haben keine gleichen Quotienten, wenn sie auf die Dezimalstelle Null korrigiert werden.
Zum Beispiel:
• 11, 13, wenn durch 3 geteilt, ergeben den eindeutigen Quotienten von 4, wenn der Quotient auf dezimale Null korrigiert wird.
• 17, 19, wenn durch 3 geteilt, ergibt den eindeutigen Quotienten von 6, wenn der Quotient auf dezimale Null korrigiert wird.
• 29, 31, wenn durch 3 geteilt, ergeben den eindeutigen Quotienten von 10, wenn der Quotient auf dezimale Null korrigiert wird.
usw.
Unten ist eine einfache Prozedur mit Excel zu:
• Finde primäre Zwillinge aus einer beliebigen Liste von Primzahlen • Finden Sie Primzahlzwillinge in einer beliebigen Anzahl von Primzahlen • Finden Sie die größte Prime Twin Prime • Finde Lücken zwischen Primzahlzwillingen
Um die größte Zwillings-Primzahl zu finden, verwende das obige Verfahren mit einem Bereich der größten bekannten Primzahl in Spalte 1 (z. B. die höchsten 10-k-Primzahlen).
Wenn in diesem Bereich kein primärer Zwilling gefunden wird, gehen Sie zum nächstniedrigeren Bereich, bis ein Zwillingsprimär gefunden wird. Dies wird die größte Doppel Prime sein.
Hoffe, das hilft.