SF (n) jest funkcją, która oblicza najmniejszy czynnik pierwszy dla danej liczby n.
Nazwiemy T (N) sumą każdej SF (n) z 2 <= n <= N.
T (1) = 0 (suma jest powyżej 0 sum)
T (2) = 2 (2 jest pierwszą liczbą pierwszą)
T (3) = 5 = 2 + 3
T (4) = 7 = 2 + 3 + 2
T (5) = 12 = 2 + 3 + 2 + 5
...
T (10000) = 5786451
Zwycięzcą zostanie ten, któremu uda się obliczyć największą T (N) w 60 sekund na własnym laptopie (Toshiba Satellite L845, Intel Core i5, 8 GB pamięci RAM).
Current top score: Nicolás Siplis - 3.6e13 points - Nim
math
fastest-code
primes
division
Nicolás Siplis
źródło
źródło
Odpowiedzi:
Nim, 3.6e13
Samo przesiewanie nie jest najlepszą odpowiedzią, gdy próbujesz obliczyć najwyższy możliwy N, ponieważ wymagania pamięci stają się zbyt wysokie. Oto inne podejście (zacząłem od Nima kilka dni temu i zakochałem się w szybkości i składni, mile widziane są wszelkie sugestie dotyczące przyspieszenia lub zwiększenia czytelności!).
źródło
return
wf
„s definicji. Procesy z pojedynczym wyrażeniem zwracają się automatycznie.C, Prime Sito: 5e9
Wyniki:
Program:
Chociaż jest to dość prosty program, zajęło mi trochę czasu, aby dowiedzieć się, jak właściwie zarządzać pamięcią - mam tylko tyle pamięci RAM na 1 bajt na liczbę w zakresie, więc musiałem być ostrożny. To standardowe sito Erasthones.
źródło
Perl, faktoring brutalny
Mogę dostać się do około 9e7 w 25 sekund na moim komputerze z systemem Linux. Może być szybsze po wkopaniu w kod C, jak to mówi po sprawdzeniu 2/3/5, całkowicie uwzględnij liczbę.
Są o wiele bardziej sprytne sposoby na to za pomocą przesiewania. Myślałem, że prosty sposób na brutalną siłę będzie początkiem. Nawiasem mówiąc, jest to zasadniczo problem dotyczący projektu Euler 521.
źródło
Idź, 21e9
Wykonuje sito, aby znaleźć minimalny współczynnik dla każdej liczby <= N. Odradza goroutines, aby policzyć części przestrzeni liczbowej.
Uruchom z „go run prime.go -P 4 -N 21000000000”.
Zauważ, że odpowiedź dla N = 21e9 zawiera się między 2 ^ 63 a 2 ^ 64, więc musiałem użyć 64-bitowych liczb całkowitych bez znaku, aby poprawnie policzyć ...
źródło
C ++, 1 << 34 ~ 1.7e10
źródło
Java 8:
1.8e82.4e8Ten wpis nie porównuje się z kilkoma innymi, które już się pojawiły, ale chciałem opublikować swoją odpowiedź, ponieważ dobrze się nad tym bawiłem.
Główne optymalizacje mojego podejścia są następujące:
T(N)
kiedyN % 2 == 1
to wiesz, wiesz o tymT(N + 1) == T(N) + 2
. Pozwala mi to rozpocząć liczenie od trzeciej i zwiększać o iterację po dwa.Collection
typie. To ponad dwukrotnie zwiększyłoN
zasięg.To wszystko. Mój kod iteruje od 3 do 2, aż wykryje, że przekroczył limit czasu, w którym to momencie wyrzuca odpowiedź.
Działa w innym systemie (Windows 8.1, Intel Core i7 @ 2,5 GHz, 8 GB RAM) z najnowszą wersją Java 8 ma znacznie lepsze wyniki bez zmian kodu:
źródło
mayContinue()
wfor loop condition
za pomocą jednego prostego warunku, można osiągnąć wyższy wynik. Podoba mi się twój sposób wstępnego obliczania nawet sumy, a następnie zwiększania o dwa.startTime
na,endTime
aby wyeliminować odejmowanie ~ 2e7, ale to kosztowało mnie 3e7 od mojego wyniku!System.nanoTime() - startTime < TIME_LIMIT
, bo to trochę poprawia twój kod. Nie jest to niesamowicie szybkie, biorąc pod uwagę fakt, że ten warunek jest sprawdzany miliony razy, będzie trochę szybki. Jednej rzeczy nauczyłem się z twojego kodu: nie wkładajfor
dofor
.. Po przejściufor
na inną metodę w moim kodzie, moja prędkość kodu wzrasta o 40%, Dzięki .. Jedną rzeczą, którą wciąż się zastanawiam jest, czy tablice są znacznie wydajniejsze niż ArrayList, biorąc pod uwagę fakt, że jest pobierany miliony razy ..x2
wynik, jeśli wdrożyszMultiThreading
. Musiałby jednak wstępnie obliczyć całą tablicę przed uruchomieniem obliczeń Prime.mayContinue()
metody do pętli for kosztuje mnie 8e6 od mojego wyniku. Może to być problem lokalnych optymalizacji. Podczas opracowywania tego rozwiązania eksperymentowałem z kilkoma typami danych do przechowywania liczb pierwszych. Byłem w stanie osiągnąć jedynie 8,8e7ArrayList
, ale uderzyłem 1,8e8 (teraz 2,4e8) za pomocą tablicy. Wyszukiwanie może wiązać się z pewnym wzrostem wydajności, ale istnieją wyraźne przyspieszenia przydziału pamięci. Myślałem o algorytmie wielowątkowości, ale napotkałem problemy.R 2,5e7
Prosto myślące sito Eratostenesa, wektoryzowane w jak największym stopniu. R tak naprawdę nie jest przeznaczony do tego rodzaju problemów i jestem pewien, że można go przyspieszyć.
źródło
sum(vec)
prowadzi do przepełnienia liczb całkowitych i zwraca NA.sum(as.numeric(vec))
podsumowuje wektor dubletów, który się nie przepełnia (choć może nie dać właściwej odpowiedzi)Python, ~ 7e8
Używając przyrostowego sita Erathostenes. Należy zachować ostrożność, aby zaznaczona wartość była oznaczona najniższym dzielnikiem, ale w przeciwnym razie implementacja jest dość prosta.
Mierzono czas w PyPy 2.6.0, dane wejściowe są akceptowane jako argument wiersza poleceń.
Przykładowe użycie
źródło
Julia, 5e7
Z pewnością Julia może sobie poradzić lepiej, ale teraz to właśnie mam. To robi 5e7 w około 60 sekund na JuliaBox, ale nie mogę jeszcze przetestować lokalnie. Mam nadzieję, że do tego czasu wymyślę bardziej sprytne podejście.
Tutaj tworzymy funkcję,
lpf
która iteruje przez sekwencyjne liczby pierwsze i sprawdza dane wejściowe pod kątem podzielności według każdego z nich. Funkcja zwraca pierwszy napotkany dzielnik, uzyskując w ten sposób najmniejszą liczbę pierwszą.Główna funkcja oblicza
lpf
na liczbach całkowitych od 2 do wejścia równolegle i zmniejsza wynik sumując.źródło
Common Lisp, 1e7
Zdecydowałem się najpierw wygenerować listę liczb pierwszych od 2 do
(sqrt input)
, a następnie przetestować każdą wartość za pomocą liczb pierwszych, podczas gdy poprzednio testowałem każdą liczbę do(sqrt input)
, co byłoby bezcelowe (np. Jeśli liczba jest podzielna przez 4, jest również podzielny przez 2, więc został już uwzględniony.)Dzięki Bogu za skutki uboczne, gdy jestem przy tym. Funkcja remove-if obniża rozmiar listy i liczy liczbę elementów, które zostały usunięte, więc muszę tylko pomnożyć to przez dowolną wartość, która jest włączona, i dodać ją do sumy bieżącej.
(Ciekawostka:
delete
jest niszczycielskim odpowiednikiemremove
, ale z jakiegokolwiek powodudelete
jest trochę wolniejszy niżremove
w tym przypadku).źródło
Rdza 1.5e9
Bardzo naiwne sito Eratosthene, ale czułem, że Rust nie otrzymał tu żadnej miłości!
źródło
Java 2.14e9
Czyste sito Eratostenesa z przewagą BitSet
Integer.MAX_VALUE - 1
Właśnie przeliczyłem sumę najmniejszego współczynnika Prime33.89 s
. Ale nie mogę przejść dalej, ponieważ dalsze doprowadzą do przepełnienia liczby całkowitej w rozmiarze zestawu bitów. Pracuję więc nad stworzeniem kolejnego zestawu bitów dla następnego zestawu zakresów. Do tego czasu jest to najszybszy, jaki mogę wygenerować.źródło