Cel jest prosty: oblicz funkcję sumaryczną dla jak największej liczby liczb w 10 sekund i zsumuj liczby.
Musisz wydrukować wynik na końcu i faktycznie go obliczyć. Żadna automatyczna funkcja totient nie jest dozwolona, ale biblioteki bignum są. Musisz zacząć od 1 i policzyć kolejno liczby całkowite. Teraz nie wolno pominąć numery.
Twój wynik to ile liczb twój program może obliczyć na twoim komputerze / ile mój program może obliczyć na twoim komputerze . Mój kod jest prostym programem w C ++ (wyłączone optymalizacje), mam nadzieję, że możesz go uruchomić.
Ważne właściwości, których możesz użyć!
- Jeśli
gcd(m,n) = 1, phi(mn) = phi(m) * phi(n)
- jeśli
p
jest liczbą pierwsząphi(p) = p - 1
(dlap < 10^20
) - jeśli
n
jest nawetphi(2n) = 2 phi(n)
- inne wymienione w pierwszym linku
Mój kod
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
int phi(int n)
{
int x = 0;
for (int i=1; i<=n; i++)
{
if (gcd(n, i) == 1)
x++;
}
return x;
}
int main()
{
unsigned int sum = 0;
for (int i=1; i<19000; i++) // Change this so it runs in 10 seconds
{
sum += phi(i);
}
cout << sum << endl;
return 0;
}
fastest-code
qwr
źródło
źródło
1, 3, 5, 2, 4
?Odpowiedzi:
Nimrod: ~ 38 667 (580 000 000/15 000)
W tej odpowiedzi zastosowano dość proste podejście. W kodzie zastosowano proste sito liczby pierwszej, które przechowuje liczbę pierwszą najmniejszej mocy liczby pierwszej w każdym gnieździe dla liczb zespolonych (zero dla liczb pierwszych), a następnie używa programowania dynamicznego do skonstruowania funkcji totient w tym samym zakresie, a następnie sumuje wyniki. Program spędza praktycznie cały czas na budowie sita, a następnie oblicza funkcję totient w ułamku czasu. Wygląda na to, że sprowadza się to do zbudowania wydajnego sita (z lekkim zwrotem, że trzeba również wyodrębnić główny czynnik dla liczb zespolonych z wyniku i utrzymać zużycie pamięci na rozsądnym poziomie).
Aktualizacja: Poprawiona wydajność poprzez zmniejszenie zajmowanego miejsca w pamięci i poprawę zachowania pamięci podręcznej. Można wycisnąć o 5% -10% większą wydajność, ale wzrost złożoności kodu nie jest tego wart. Ostatecznie algorytm ten przede wszystkim wykorzystuje wąskie gardło procesora von Neumanna i istnieje bardzo niewiele poprawek algorytmicznych, które mogą to obejść.
Zaktualizowałem również dzielnik wydajności, ponieważ kod C ++ nie miał być kompilowany przy wszystkich optymalizacjach i nikt tego nie zrobił. :)
Aktualizacja 2: Zoptymalizowane działanie sita dla lepszego dostępu do pamięci. Teraz obsługa dużych liczb pierwszych za pomocą memcpy () (przyspieszenie ~ 5%) i pomijanie wielokrotności 2, 3 i 5 podczas przesiewania większych liczb pierwszych (przyspieszenie ~ 10%).
Kod C ++: 9,9 sekundy (z g ++ 4.9)
Kod Nimrod: 9,9 sekundy (z -d: release, backend gcc 4.9)
źródło
Java, wynik ~ 24 000 (360 000 000/15 000)
Poniższy kod Java oblicza razem funkcję totient i sito główne. Zauważ, że w zależności od twojego komputera musisz zwiększyć początkową / maksymalną wielkość sterty (na moim raczej wolnym laptopie musiałem iść do góry
-Xmx3g -Xms3g
).źródło
Nimrod: ~ 2 333 333 (42 000 000 000/18 000)
To używa zupełnie innego podejścia niż moja poprzednia odpowiedź. Zobacz komentarze, aby uzyskać szczegółowe informacje.
longint
Moduł można znaleźć tutaj .źródło
2*sqrt(n)
), co oznacza znacznie niższy wynik.C #: 49 000 (980 000 000/20 000)
/codegolf//a/26800 „Kod Howarda”.
Ale zmodyfikowane wartości ph są obliczane dla nieparzystych liczb całkowitych.
Nowy wynik: 61 000 (1 220 000 000/20 000)
W „App.config” musiałem dodać „gcAllowVeryLargeObjects enabled = true”.
źródło
Python 3: ~ 24000 (335 000 000/14 000)
Moja wersja to port Pythona algorytmu Howarda . Moją oryginalną funkcją była modyfikacja algorytmu wprowadzona na tym blogu .
Używam modułów Numpy i Numba, aby przyspieszyć czas wykonywania. Zauważ, że normalnie nie musisz deklarować typów zmiennych lokalnych (przy użyciu Numba), ale w tym przypadku chciałem maksymalnie skrócić czas wykonania.
Edycja: połączone funkcje buildsieve i summarum w jedną funkcję.
C ++: 9,99 s (n = 14 000); Python 3: 9,94s (n = 335 000 000)
źródło
Oto moja implementacja w języku Python, która wydaje się być w stanie wykręcić ~ 60000 liczb w ciągu 10 sekund. Faktoryzuję liczby za pomocą algorytmu rovera i za pomocą testu pierwotności Millera.
źródło
φ (2 n ) = 2 n - 1
Σ φ (2 i ) = 2 i - 1 dla i od 1 do n
Po pierwsze, coś do znalezienia razy:
Dla mnie kod referencyjny to:
Haskell:
Robi coś z 2525224 cyframi w 0,718 sekundy. A teraz zauważam komentarz @ Howarda.
źródło
Matlab: 1464 = 26355867/18000
Nie mogę przetestować twojego kodu, więc podzieliłem go na 18000, ponieważ jest to najszybszy komputer spośród testujących. Doszedłem do zapisu przy użyciu tej właściwości:
Najbardziej podoba mi się to, że jest to jedna wkładka:
źródło
phi(p)
na wszystkich nie-najlepszychp
?Python 2.7: 10.999 (165975/15090)
Pypy 2.3.1: 28.496 (430000/15090)
Kilka interesujących metod, których używam:
Silny test Pseudoprime Rabin-Millera - test pierwotności, który zapewnia skuteczny algorytm probabilistyczny do określania, czy dana liczba jest liczbą pierwszą
Formuła produktu Eulera - iloczyn liczbowy jest różny od liczb pierwszych dzielących n
Kod:
źródło