Definicja
Liczba jest dodatnia, jeśli jest większa od zera.
Liczba ( A
) jest dzielnikiem innej liczby ( B
), jeśli A
można podzielić B
bez reszty.
Na przykład 2
jest dzielnikiem, 6
ponieważ 2
można podzielić 6
bez reszty.
Cel
Twoim zadaniem jest napisanie programu / funkcji, która przyjmuje liczbę dodatnią, a następnie znalezienie wszystkich jej dzielników.
Ograniczenie
- Nie możesz używać żadnych wbudowanych funkcji związanych z liczbą pierwszą lub faktoryzacją .
- Złożoność algorytmu nie może przekraczać O (sqrt (n)) .
Wolność
- Lista wyjściowa może zawierać duplikaty.
- Lista wyników nie musi być sortowana.
Punktacja
To jest golf golfowy . Najkrótsze rozwiązanie w bajtach wygrywa.
Przypadki testowe
input output
1 1
2 1,2
6 1,2,3,6
9 1,3,9
O(sqrt(n))
.99 (1 3 9 11 33 99)
Odpowiedzi:
PostgreSQL, 176 bajtów
SqlFiddleDemo
Wejście:
(SELECT ...v)
Jak to działa:
(SELECT ...v)
- Wejściegenerate_series(1, sqrt(v)::int)
- liczby od 1 do sqrt (n)WHERE v%r=0
- dzielniki filtrówSELECT r FROM c UNION SELECT v/r FROM c
generete reszta dzielników i łączSELECT string_agg(r::text,',' ORDER BY r)
tworzy końcowy wynik oddzielony przecinkamiWprowadź jako tabelę:
SqlFiddleDemo
Wynik:
źródło
C # 6, 75 bajtów
Oparty na rozwiązaniu C # downrep_nation, ale rekurencyjny i grał w golfa dalej, wykorzystując kilka nowych funkcji z C # 6.
Podstawowy algorytm jest taki sam jak ten przedstawiony przez downrep_nation. Pętla for zamienia się w rekurencję, a więc drugi parametr. start rekurencji odbywa się za pomocą parametru domyślnego, dlatego funkcja jest wywoływana tylko z wymaganym pojedynczym numerem początkowym.
Ponieważ większość odpowiedzi tutaj (jeszcze) nie jest zgodna z dokładnym formatem wyjściowym z przykładów, zachowuję go takim, jaki jest, ale wadą jest, że wynik zawiera pojedynczy przecinek końcowy.
źródło
R ,
3631 bajtówWypróbuj online!
-5 bajtów dzięki Robin Ryder
źródło
n^.5
zamiastsqrt(n)
.1
wiele razy.Matlab, 48 bajtów
źródło
sqrt(n)
a następnie umieszczam każdy dzielnikd
in/d
na mojej liście.b=~mod(n,a)
zapisać 1 bajtu?J, 26 bajtów
Wyjaśnienie
źródło
JavaScript (ES6) - 48 bajtów
Niezbyt wydajny, ale działa! Przykład poniżej:
źródło
MATL , 12 bajtów
Podejście jest podobne do tego w odpowiedzi @ flawr .
Wypróbuj online!
Wyjaśnienie
źródło
05AB1E ,
1412 bajtówKod:
Wyjaśnienie:
Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .
źródło
Python 2, 64 bajty
Ta anonimowa funkcja generuje listę dzielników. Dzielniki są obliczane przez próbny podział liczb całkowitych z zakresu
[1, ceil(sqrt(n))]
, który jestO(sqrt(n))
. Jeślin % x == 0
(równoważnikn%x<1
), a następnie obax
in/x
są dzielnikamin
.Wypróbuj online
źródło
Galaretka , 9 bajtów
Podobnie jak inne odpowiedzi, jest to O (√n), jeśli przyjmiemy (fałszywe) założenie, że dzielenie liczb całkowitych to O (1) .
Jak to działa
Wypróbuj online!
źródło
JavaScript, 47 bajtów
źródło
Mathematica, 50 bajtów
Podobne do rozwiązania @ flawr .
Wykonuje podział szlaku dla x od 1 do pierwiastka kwadratowego z n, a jeśli jest podzielny, zapisuje go na liście jako x i n / x .
∣
wymaga 3 bajtów do reprezentowania w UTF-8, dzięki czemu 48-znakowy ciąg wymaga 50 bajtów w reprezentacji UTF-8.Stosowanie
źródło
JavaScript (ES6),
6662 bajtówMyślałem, że napiszę wersję, która zwróciła posortowaną listę deduplikacji, i okazało się, że jest o 4 bajty krótsza ...
źródło
C #, 87 bajtów
Grał w golfa
Nie golfił
Pełny kod
Wydawnictwa
87 bytes
- Wstępne rozwiązanie.Notatki
var
„iint
” zamiastString
„iInt32
”, aby kod był krótszy, natomiast w kodzie „Ungolfed” i pełnym kodzie używamString
„iInt32
”, aby kod był bardziej czytelny.źródło
for
jest to ogólnie lepsze niżwhile
.for
pętla miałaby taką samą długość jakwhile
pętla. W tym przypadku nie ma znaczenia posiadanie drugiego.Lua, 83 bajty
Niestety nie mogłem nic lepszego
źródło
Perl 6 , 40 bajtów
Wyjaśnienie:
Stosowanie:
źródło
c #, 87 bajtów
nie wiem, czy to działa na wszystkie liczby, podejrzewam, że tak.
ale złożoność jest słuszna, więc to już coś nie jest
źródło
Rubinowy, 56 bajtów
źródło
Kod maszynowy IA-32, 27 bajtów
Hexdump:
Kod źródłowy (składnia MS Visual Studio):
Pierwszy parametr (
ecx
) to wskaźnik do wyjścia, drugi parametr (edx
) to liczba. W żaden sposób nie oznacza końca wyniku; należy wypełnić tablicę wyjściową zerami, aby znaleźć koniec listy.Pełny program C ++ korzystający z tego kodu:
Dane wyjściowe mają pewne usterki, mimo że są zgodne ze specyfikacją (nie ma potrzeby sortowania; nie ma potrzeby wyjątkowości).
Dane wejściowe: 69
Wynik:
Dzielniki są w parach.
Wejście: 100
Wynik:
Aby uzyskać idealne kwadraty, ostatni dzielnik jest wyprowadzany dwukrotnie (jest to para ze sobą).
Wejście: 30
Wynik:
Jeśli dane wejściowe są zbliżone do idealnego kwadratu, ostatnia para jest wysyłana dwukrotnie. Wynika to z kolejności sprawdzania w pętli: najpierw sprawdza „resztę = 0” i wypisuje, a dopiero potem sprawdza „iloraz <dzielnik”, aby wyjść z pętli.
źródło
SmileBASIC, 49 bajtów
Wykorzystuje fakt, że
D>N/D
=D>sqrt(N)
dla liczb dodatnichźródło
C,
8781 bajtówPoprawiony przez @ceilingcat , 81 bajtów:
Wypróbuj online!
Moja oryginalna odpowiedź, 87 bajtów:
Kompiluj
gcc div.c -o div -lm
i uruchamiaj z./div <n>
.Bonus: jeszcze krótszy wariant ze złożonością czasową O (n) i zakodowany na stałe
n
(46 bajtów + długośćn
):Edycja: Dziękuję @Sriotchilism O'Zaic za wskazanie, że dane wejściowe nie powinny być zakodowane na stałe, zmodyfikowałem główne przesłanie, aby pobrać dane za pośrednictwem argv.
źródło
n
dane wejściowe? Umieszczanie danych wejściowych w zmiennej nie jest tutaj przyjętym sposobem z wielu powodów. Możesz dowiedzieć się więcej o naszych przyjętych i non-Przyjmujemy tu wejściowych i wyjściowych: codegolf.meta.stackexchange.com/questions/2447/... . A jeśli interesuje Cię konkretny język (np. C), możesz zajrzeć tutaj: codegolf.meta.stackexchange.com/questions/11924/… .n
to dane wejściowe. Spróbuję go zmodyfikować, aby pobierał dane wejściowe w inny sposób. Dziękuję za informację!APL (NARS), 22 znaki, 44 bajty
test:
źródło
C # (interaktywny kompilator Visual C #) , 40 bajtów
Wystarczy podać zaktualizowaną odpowiedź w języku C #
Wypróbuj online!
źródło