Właściwa dzielnik jest dzielnikiem z szeregu N , które nie są n siebie. Na przykład odpowiednimi dzielnikami 12 są 1, 2, 3, 4 i 6.
Otrzymasz liczbę całkowitą x , x ≥ 2, x ≤ 1000 . Twoim zadaniem jest zsumowanie wszystkich najwyższych właściwych dzielników liczb całkowitych od 2 do x (włącznie) (OEIS A280050 ).
Przykład (z x = 6
):
Znajdź wszystkie liczby całkowite od 2 do 6 (włącznie): 2,3,4,5,6.
Zdobądź odpowiednie dzielniki wszystkich i wybierz najwyższe z każdej liczby:
- 2 -> 1
- 3 -> 1
- 4 -> 1, 2
- 5 -> 1
- 6 -> 1, 2, 3 .
Podsumowując najwyższe odpowiednie dzielniki:
1 + 1 + 2 + 1 + 3 = 8
.Ostateczny wynik to 8.
Przypadki testowe
Wejście | Wynik ------- + --------- | 2 | 1 4 | 4 6 | 8 8 | 13 15 | 41 37 | 229 100 | 1690 1000 | 165279
Zasady
Możesz pobierać dane wejściowe i dostarczać dane wyjściowe dowolną standardową metodą .
To jest golf golfowy , wygrywa najkrótszy ważny zgłoszenie w każdym języku! Baw się dobrze!
Odpowiedzi:
Oaza , 4 bajty
Kod:
Wypróbuj online!
Wyjaśnienie:
Rozszerzona wersja:
źródło
Łuska , 7 bajtów
Wypróbuj online!
Wyjaśnienie
Husk nie ma wbudowanego (jeszcze) obliczania dzielników bezpośrednio, więc zamiast tego używam faktoryzacji pierwotnej. Największy właściwy dzielnik liczby jest iloczynem jego głównych czynników, z wyjątkiem najmniejszego. Mapuję tę funkcję w zakresie od 2 do danych wejściowych i sumuję wyniki.
źródło
Python 2 , 50 bajtów
Jest to powolne i nawet nie radzi sobie z wejściem 15 na TIO.
Wypróbuj online!
Jednak do weryfikacji wszystkich przypadków testowych można wykorzystać notatkę ( dzięki @ musicman523 ).
Wypróbuj online!
Alternatywna wersja, 52 bajty
Kosztem 2 bajtów możemy wybrać, czy obliczyć,
f(n,k+1)
czyn/k+f(n-1)
.Z pewnymi podstępami działa to dla wszystkich przypadków testowych, nawet w TIO.
Wypróbuj online!
źródło
f
jest to czysta funkcja , możesz ją zapamiętać, aby uruchamiać większe skrzynki na TIOGalaretka , 6 bajtów
Wypróbuj online!
Jak to działa
źródło
Brachylog , 10 bajtów
Wypróbuj online!
źródło
JavaScript (ES6), 40 bajtów
Liczba równa się iloczynowi jej najwyższego właściwego dzielnika i najmniejszego czynnika pierwszego.
źródło
n>352
(przynajmniej w tym fragmencie, nie wiem, czy jest to zależność mojej przeglądarki / maszyny), podczas gdy powinieneś wspierać przynajmniej upton=1000
.n=1000
jeśli używasz npnode --stack_size=8000
.05AB1E ,
98 bajtów-1 dzięki Byte do nieszczelnego Nun „s czynnik pierwszy trik w swoim Pyth odpowiedź
Wypróbuj online!
Wyjaśnienie
Alternatywne rozwiązanie 8-bajtowe (to nie działa na TIO)
i ofc alternatywne rozwiązanie 9-bajtowe (które działa na TIO)
źródło
Retina ,
3124 bajtów7 bajtów dzięki Martinowi Enderowi.
Wypróbuj online!
Jak to działa
Wyrażenie regularne
/^(1+)\1+$/
przechwytuje największy właściwy dzielnik o określonej liczbie reprezentowany w jedności. W kodzie\1+
zmieniono na składnię lookahead.źródło
Mathematica, 30 bajtów
źródło
Pyth ,
1398 bajtów1 bajt dzięki Jacoblaw.
Zestaw testowy .
Jak to działa
Największy właściwy dzielnik jest iloczynem czynników pierwszych, z wyjątkiem najmniejszego.
źródło
Python 2 (PyPy) ,
737170 bajtówNie jest to najkrótsza odpowiedź w języku Python, ale po prostu przegląda przypadki testowe. TIO obsługuje wejścia do 30 000 000 bez zerwania potu; mój komputer stacjonarny obsługuje 300 000 000 minut.
Kosztem 2 bajtów warunek
n>d
może być wykorzystany do przyspieszenia o ~ 10%.Dzięki @xnor za
r=[0]*n
pomysł, który oszczędził 3 bajty!Wypróbuj online!
źródło
l=[0]*n
powinien pozwolić ci się pozbyć-2
.exec
trochę zabija prędkość, ale nawetwhile
pętla byłaby krótsza niż moje podejście.Haskell,
484643 bajtówWypróbuj online!
Edycja: @rogaos zapisał dwa bajty. Dzięki!
Edytuj II: ... i @xnor kolejne 3 bajty.
źródło
f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
sum
, więc pomyślałem, że nie jest krótsza.until
oszczędza trochę więcej:until((<1).mod n)pred(n-1)+f(n-1)
Japt ,
8 + 2 = 1086 bajtówSprawdź to
Wyjaśnienie
źródło
-x
liczy się jako dwa bajty zgodnie z tym postem . Myślę jednak, że można zapisać bajt za pomocąò2_â1 o
(â
wyklucza oryginalny numer, gdy podano argument)â
argumentu przyniosło mi oszczędności, których szukałem.õ Å
przed i znalazłem parę 8- i 9-byters:õ Åx_/k g
,õ Åx_k Å×
,õ Åx_â¬o
. I łączącõ
iÅ
ze swoim geniusxo
sztuczki znalazłem rozwiązanie 7-bajtowy :-)MATL, 12 bajtów
Wypróbuj w MATL Online
Wyjaśnienie
źródło
PHP , 56 bajtów
Wypróbuj online!
źródło
Prolog (SWI) , 72 bajty
Wypróbuj online!
źródło
Cubix , 27
39bajtówWypróbuj online!
Cubified
Watch It Run
0IU
Ustaw stos z akumulatorem i początkową liczbą całkowitą. Zawracanie w zewnętrzną pętlę:(?
zduplikuj bieżącą górę stosu, zmniejszenie i test\pO@
jeśli zero pętli wokół sześcianu do lustra, złap dno stosu, wyjście i zatrzymaj%\!
jeśli pozytywne, mod, relect i test.u;.W
jeśli to prawda, należy zawracać, usuwać wynik mod i zmienić pas z powrotem w wewnętrzną pętlęU;p+qu;;\(
jeśli falsey, zawracanie, usuń wynik mod, przenieś akumulator na górę, dodaj bieżącą liczbę całkowitą (górną) wciśnij do dołu i zawróć. Oczyść stos, aby mieć tylko akumulator i bieżącą liczbę całkowitą, zmniejsz liczbę całkowitą i ponownie wejdź do zewnętrznej pętli.źródło
C # (.NET Core) ,
7472 bajtyWypróbuj online!
źródło
break
w golfaj=0
.Właściwie 12 bajtów
Wypróbuj online!
źródło
Python 3 ,
78 75 7371 bajtówNawet w pobliżu pythonowej nieszczelnej odpowiedzi zakonnicy w liczbie bajtów.
Wypróbuj online!
źródło
Python 3 ,
696359 bajtów4 bajty dzięki Dennisowi.
Wypróbuj online!
Ustawiłem limit rekurencji na 2000, aby działało to dla 1000.
źródło
Węgiel drzewny , 37 bajtów
Wypróbuj online!
Link jest do pełnej wersji. Prawie cały dzień zajęło mi ustalenie, w jaki sposób mogę rozwiązać pytanie niezwiązane ze sztuką ASCII w Charcoal, ale w końcu je zrozumiałem i jestem z niego bardzo dumny. :-RE
Tak, jestem pewien, że można w to dużo grać w golfa. Właśnie przetłumaczyłem moją odpowiedź w języku C # i jestem pewien, że w Charcoal można to zrobić inaczej. Przynajmniej rozwiązuje
1000
sprawę w ciągu kilku sekund ...źródło
Pari / GP ,
3630 bajtówWypróbuj online!
źródło
Python 2 (PyPy) , 145 bajtów
Ponieważ przekształcanie zawodów w golfa w zawody z najszybszym kodem jest fajne, oto algorytm O ( n ), który w TIO rozwiązuje n = 5 000 000 000 w 30 sekund. ( Sito Dennisa to O ( n log n ).)
Wypróbuj online!
Jak to działa
Liczymy rozmiar zestawu
S = {( a , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ największy dzielnik właściwy ( a )},
przepisując go jako sumę, dla wszystkich liczb pierwszych p ≤ √n, z
S p = {( p ⋅ d , b ) | 2 ≤ d ≤ n / p , 2 ≤ b ≤ d },
i stosując zasadę włączenia / wyłączenia :
| S | = ∑ (−1) m - 1 | S p 1 ∩ ⋯ ∩ S p m | powyżej m ≥ 1 i liczb pierwszych p 1 <⋯ < p m ≤ √n,
gdzie
S p 1 ∩ ⋯ ∩ S p m = {( p 1 ⋯ p m ⋅ e , b ) | 1 ≤ e ≤ n / ( p 1 ⋯ p m ), 2 ≤ b ≤ p 1 ⋯ p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1 ⋯ p m ) ⌋⋅ ( p 1 ⋯p m - 1 ⋅ (⌊ n / ( p 1 ⋯ p m ) ⌋ + 1) - 2) / 2.
Suma ma C ⋅ n niezerowe warunki, gdzie C jest zbieżne do pewnej stałej, która prawdopodobnie wynosi 6⋅ (1 - 1 n 2) / π 2 ≈ 0,186544. Ostateczny wynik to | S | + n - 1.
źródło
NewStack , 5 bajtów
Na szczęście w rzeczywistości jest wbudowany.
Podział:
W aktualnym języku angielskim:
Uruchommy przykład dla danych wejściowych 8.
Nᵢ
: Zrób listę liczb naturalnych od 1 do 8:1, 2, 3, 4, 5, 6, 7, 8
;
: Oblicz największe czynniki:1, 1, 1, 2, 1, 3, 1, 4
q
. Usuń pierwszy element:1, 1, 2, 1, 3, 1, 4
Σ
I weź sumę:1+1+2+1+3+1+4
=13
źródło
1+1+2+1+3+1+4
=13
nie8
. Poza tym: świetna odpowiedź, więc +1.Java 8,
787472 bajtyPort odpowiedzi C # @CarlosAlejo .
Wypróbuj tutaj.
Stara odpowiedź (78 bajtów):
Wypróbuj tutaj.
Objaśnienie (starej odpowiedzi):
źródło
Lua , 74 bajty
Wypróbuj online!
źródło
J , 18 bajtów
Wypróbuj online!
źródło
Ułożone , 31 bajtów
Wypróbuj online! (Wszystkie przypadki testowe z wyjątkiem 1000, które przekraczają 60-sekundowy limit czasu online).
Wyjaśnienie
źródło
C (gcc) , 53 bajty
Wypróbuj online!
Wygodnie i szybko mija wszystkie przypadki testowe.
źródło