SF (n) ist eine Funktion, die den kleinsten Primfaktor für eine gegebene Zahl n berechnet.
Wir nennen T (N) die Summe jedes SF (n) mit 2 <= n <= N.
T (1) = 0 (die Summe ist über 0 Summanden)
T (2) = 2 (2 ist die erste Primzahl)
T (3) = 5 = 2 + 3
T (4) = 7 = 2 + 3 + 2
T (5) = 12 = 2 + 3 + 2 + 5
...
T (10000) = 5786451
Der Gewinner ist derjenige, der es schafft, die größte T (N) in 60 Sekunden auf meinem eigenen Laptop (Toshiba Satellite L845, Intel Core i5, 8 GB RAM) zu berechnen.
Current top score: Nicolás Siplis - 3.6e13 points - Nim
math
fastest-code
primes
division
Nicolás Siplis
quelle
quelle
Antworten:
Nim, 3,6e13
Ein einfaches Sieben ist nicht die beste Antwort, wenn versucht wird, den höchstmöglichen N-Wert zu berechnen, da der Speicherbedarf zu hoch wird. Hier ist ein anderer Ansatz (hat vor ein paar Tagen mit Nim angefangen und sich in die Geschwindigkeit und Syntax verliebt. Vorschläge, die es schneller oder lesbarer machen, sind willkommen!).
quelle
return
inf
Definition. Einzelne Ausdrücke werden automatisch zurückgegeben.C, Prime Sieve: 5e9
Ergebnisse:
Programm:
Obwohl es sich um ein recht einfaches Programm handelt, habe ich eine Weile gebraucht, um herauszufinden, wie ich die Speicherverwaltung richtig machen kann. Ich habe nur genug RAM für 1 Byte pro Nummer im Bereich, also musste ich vorsichtig sein. Es ist ein Standardsieb von Erasthones.
quelle
Perl, Brute Force Factoring
Auf meinem Linux-Rechner kann ich in 25 Sekunden ungefähr 9e7 erreichen. Durch Eingraben in den C-Code könnte es schneller gehen, da nach einer Prüfung auf 2/3/5 die Zahl vollständig berücksichtigt wird.
Es gibt viel cleverere Möglichkeiten, dies durch Sieben zu erreichen. Ich dachte, ein einfacher Brute-Force-Weg wäre ein Anfang. Dies ist übrigens im Grunde Project Euler Problem 521.
quelle
Los, 21e9
Führt ein Sieb durch, um den Mindestfaktor jeder Zahl <= N zu ermitteln. Löst Goroutinen aus, um Abschnitte des Zahlenraums zu zählen.
Führen Sie "go run prime.go -P 4 -N 21000000000" aus.
Beachten Sie, dass die Antwort für N = 21e9 zwischen 2 ^ 63 und 2 ^ 64 liegt, sodass ich vorzeichenlose 64-Bit-Ints verwenden musste, um richtig zu zählen ...
quelle
C ++, 1 << 34 ~ 1,7e10
quelle
Java 8:
1.8e82.4e8Dieser Eintrag ist nicht mit einigen anderen Einträgen vergleichbar, aber ich wollte meine Antwort posten, da es mir Spaß gemacht hat, daran zu arbeiten.
Die Hauptoptimierungen meines Ansatzes sind wie folgt:
T(N)
wannN % 2 == 1
, wissen Sie dasT(N + 1) == T(N) + 2
. Dies ermöglicht es mir, mit dem Zählen um drei zu beginnen und durch Iteration um zwei zu erhöhen.Collection
Typ. Das hat sich mehr als verdoppelt, alsN
ich erreichen kann.Das ist ungefähr alles, was es zu tun gibt. Mein Code iteriert ab 3 zu zweit, bis er feststellt, dass er das Zeitlimit erreicht oder überschritten hat. Zu diesem Zeitpunkt gibt er die Antwort aus.
Das Ausführen auf einem anderen System (Windows 8.1, Intel Core i7 bei 2,5 GHz, 8 GB RAM) mit der neuesten Version von Java 8 führt zu deutlich besseren Ergebnissen ohne Codeänderungen:
quelle
mayContinue()
infor loop condition
mit nur einem einfachen Zustand, könnte man höheres Ergebnis erzielen. Und ich mag es, wenn Sie eine gerade Summe vorberechnen und dann um zwei erhöhen.startTime
auf eineendTime
umzustellen, um die ~ 2e7-Subtraktionen zu eliminieren, aber das hat mich 3e7 von meiner Punktzahl gekostet!System.nanoTime() - startTime < TIME_LIMIT
probiert, weil es deinen Code für mich ein wenig beschleunigt. Es ist nicht blitzschnell, wenn man bedenkt, dass dieser Zustand millionenfach überprüft wird, es wird ein bisschen schnell. Eine Sache , die ich aus dem Code gelernt wird, nicht gesetztfor
innerhalb einesfor
.. Nach dem Umzugfor
in meinem Code auf eine andere Methode, meinen Code Geschwindigkeit um 40% erhöht wird, Dank .. Eine Sache , ich bin immer noch herauszufinden , ist, Did Arrays sind viel effizienter als ArrayList, wenn man bedenkt, dass es millionenfach abgerufen wurde.x2
Ergebnis erzielen, wenn Sie implementierenMultiThreading
. Es müsste jedoch das gesamte Array vorberechnet werden, bevor die Prime-Berechnung ausgeführt werden kann.mayContinue()
Methode in die for-Schleife kostet mich 8e6 von meiner Punktzahl. Dies kann ein Problem lokaler Optimierungen sein. Bei der Entwicklung dieser Lösung habe ich mit verschiedenen Datentypen zum Speichern der Primzahlen experimentiert. Ich war nur in der Lage, 8.8e7 mit zu erreichenArrayList
, aber ich schlug 1.8e8 (jetzt 2.4e8) unter Verwendung eines Arrays. Es kann einige Leistungssteigerungen geben, die mit dem Nachschlagen verbunden sind, aber es gibt bestimmte Steigerungen für die Speicherzuweisung. Ich habe über das Multithreading des Algorithmus nachgedacht, bin aber auf Probleme gestoßen.R, 2,5e7
Einfaches Sieb von Eratosthenes, so oft wie möglich vektorisiert. R ist nicht wirklich für diese Art von Problem ausgelegt und ich bin mir ziemlich sicher, dass es schneller gemacht werden kann.
quelle
sum(vec)
führt also für große Werte von MAX zu einem Überlauf von ganzen Zahlen und gibt NA zurück.sum(as.numeric(vec))
summiert einen doppelten Vektor, der nicht überläuft (obwohl er möglicherweise nicht die richtige AntwortPython, ~ 7e8
Verwenden eines inkrementellen Siebs von Erathostenes. Es muss sorgfältig darauf geachtet werden, dass ein markierter Wert mit dem niedrigsten Divisor markiert wird, ansonsten ist die Implementierung jedoch recht einfach.
Das Timing wurde mit PyPy 2.6.0 durchgeführt, die Eingabe wird als Befehlszeilenargument akzeptiert.
Beispielnutzung
quelle
Julia, 5e7
Sicher kann Julia es besser machen, aber das ist es, was ich jetzt habe. Dies macht 5e7 in ca. 60 Sekunden auf JuliaBox, aber ich kann lokal noch nicht testen. Hoffentlich habe ich mir bis dahin einen klügeren Ansatz überlegt.
Hier erstellen wir eine Funktion
lpf
, die durch sequenzielle Primzahlen iteriert und die Eingabe auf Teilbarkeit durch jede überprüft. Die Funktion gibt den ersten gefundenen Divisor zurück und erhält so den niedrigsten Primfaktor.Die Hauptfunktion berechnet
lpf
parallel die Ganzzahlen von 2 bis zur Eingabe und reduziert das Ergebnis durch Summieren.quelle
Common Lisp, 1e7
Ich habe mich dafür entschieden, zuerst eine Liste von Primzahlen von 2 bis zu generieren
(sqrt input)
und dann jeden Wert mit den Primzahlen zu testen, während ich zuvor gegen jede Zahl bis zu testen würde(sqrt input)
zu testete, was sinnlos wäre (zB wenn eine Zahl durch 4 teilbar ist, es ist auch durch 2 teilbar, es ist also bereits berücksichtigt.)Gott sei Dank für die Nebenwirkungen, während ich dabei bin. Das Entfernen-Wenn verringert die Größe der Liste und zählt, wie viele Elemente entfernt wurden. Ich muss also nur diesen Wert mit dem Wert multiplizieren, auf dem die Schleife aktiviert ist, und diesen Wert zur laufenden Summe hinzufügen.
(Unterhaltsame Tatsache:
delete
ist das destruktive Äquivalent vonremove
, aber aus welchem Grund auch immer,delete
ist alles viel langsamer alsremove
in diesem Fall.)quelle
Rust 1.5e9
Ein sehr naives Eratosthene-Sieb, aber ich hatte das Gefühl, dass Rust hier keine Liebe erhielt!
quelle
Java 2.14e9
Reines Eratosthenesieb mit BitSet-Vorteil
Ich habe die Summe der kleinsten Primfaktoren bis
Integer.MAX_VALUE - 1
genau in berechnet33.89 s
. Größer kann ich aber nicht vorgehen, da sonst ein Integer Overflow bei der Größe des Bitsets auftritt. Also arbeite ich daran, ein weiteres Bitset für die nächsten Ranges zu erstellen. Bis dahin ist dies die schnellste, die ich generieren kann.quelle