To wyzwanie jest na tyle prosta, że to w zasadzie wszystko w tytule: jesteś pozytywnie całkowitą N i należy zwrócić najmniejszą dodatnią liczbę całkowitą, która nie jest dzielnikiem N .
Przykład: dzielniki N = 24 to 1, 2, 3, 4, 6, 8, 12, 24
. Najmniejsza dodatnia liczba całkowita, której nie ma na tej liście, to 5 , więc taki wynik powinien znaleźć twoje rozwiązanie.
Jest to sekwencja OEIS A007978 .
Zasady
Możesz napisać program lub funkcję i użyć dowolnej z naszych standardowych metod otrzymywania danych wejściowych i dostarczania danych wyjściowych.
Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.
To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź - mierzona w bajtach .
Przypadki testowe
Pierwsze 100 warunków to:
2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2,
3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3,
2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2,
3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3
W szczególności upewnij się, że twoja odpowiedź działa dla danych wejściowych 1 i 2, w którym to przypadku wynik jest większy niż dane wejściowe.
A w przypadku niektórych większych przypadków testowych:
N f(N)
1234567 2
12252240 19
232792560 23
źródło
Odpowiedzi:
Mathematica, 19 bajtów (kodowanie UTF-8)
Nienazwana funkcja przyjmująca niezerowy argument liczby całkowitej i zwracająca dodatnią liczbę całkowitą. Pionowy pasek mniej więcej w połowie jest w rzeczywistości trzy bajtowym znakiem U + 2223, co oznacza relację podzielności w Mathematica. Wyjaśnienie:
Edytowane w celu dodania: ngenisis wskazuje, że
//.
domyślnie iteruje maksymalnie 65536 razy. Tak więc ta implementacja działa dla wszystkich liczb wejściowych mniejszych niż najmniej wspólna wielokrotność liczb całkowitych od 1 do 65538 (w szczególności dla wszystkich liczb z co najwyżej 28436 cyfr), ale technicznie nie dla wszystkich liczb. Można wymienićx//.y
zReplaceRepeated[x,y,MaxIterations->∞]
naprawić tę wadę, ale oczywiście kosztem 34 dodatkowych bajtów.źródło
For
,While
itpPyth, 3 bajty
Zasadniczo
f
zapętla kod, dopóki%QT
(Q % T
gdzieT
jest zmienna iteracyjna) nie będzie prawdą.Wypróbuj online tutaj.
źródło
.V1In%Qb0bB
zobaczyłem twoją odpowiedź i nie czułem się już tak niesamowicie.JavaScript (ES6),
2523 bajtówUwaga: Jedną interesującą rzeczą jest to, że
k
parametr jest inicjowany ex nihilo przy pierwszej iteracji. Działan % undefined
to, ponieważ jestNaN
(fałsz zgodnie z oczekiwaniami) i-~undefined
równa się1
. W następnych iteracjach-~k
jest zasadniczo równoważny zk+1
.Test
Pokaż fragment kodu
źródło
Python,
433635 bajtówźródło
Sześciokąt , 12 bajtów
Embiggened:
Wypróbuj online!
źródło
R, 28 bajtów
Całkiem proste, nic szczególnego. Pobiera dane wejściowe ze stdin, zwiększa wartość,
T
ażi
moduloT
jest niezerowe.Jeśli chcesz czegoś bardziej fantazyjnego, na 29 bajtów są następujące :
Wyjaśniono:
źródło
which.min
, ale potem zobaczyłem edycję i wygląda na to, żematch
działa podobnie.T
, oszczędzając potrzebę definiowania jej przedwhile
pętlą.while
podejście, co jest w porządku, ponieważ wymaga dużej pamięci dla dużych N.T
Sztuczka jest jedną z tych smakołyków, która jest świetna do gry w golfa, ale absolutnie okropna dla faktycznego programowania. (I oczywiście możesz użyćF
również, gdy potrzebujesz a0
.)%%
ma pierwszeństwo przed+
, więc pareny są nadal potrzebne:,(0:i+1)
z taką samą liczbą bajtów jak1:(i+1)
. Tak naprawdę pierwotnie miałem tę pierwszą, ale zmieniłem ją na drugą, ponieważ jest łatwiejsza do odczytania.Haskell, 26 bajtów
Każdy zapomina o
until
!źródło
Brachylog , 10 bajtów
Wypróbuj online!
Okazało się, że jest bardzo podobne (ale krótsze niż) oryginalne rozwiązanie Fatalize. Od tego czasu Fatalize przeszedł na inny algorytm, który łączy się z tym algorytmem za pomocą innej metody, więc muszę to wyjaśnić sam:
Kiedy odwracamy funkcję, zamieniając „wejście” i „wyjście”, otrzymujemy dość rozsądny algorytm (po prostu wyrażony w niezręczny sposób): „wypróbuj możliwe liczby całkowite dodatnie, w ich naturalnej kolejności (tj. 1 w górę), aż znajdziesz taki, którego nie można pomnożyć przez cokolwiek, aby uzyskać dane wejściowe ". Brachylog nie wykonuje obliczeń zmiennoprzecinkowych, chyba że wszystkie dane wejściowe są znane, więc uwzględni tylko liczbę całkowitą A.
źródło
Brachylog ,
1110 bajtówWypróbuj online!
Wyjaśnienie
źródło
COW, 174 bajty
Wypróbuj online!
Ten kod jest tylko częściowo moim własnym - implementuje algorytm modułu, który przeniosłem z pracy z mózgiem. Reszta kodu jest moja. Ponieważ jednak nie napisałem algorytmu modułu, tak naprawdę nie zbadałem, jak to działa i nie mogę udokumentować tej części kodu. Zamiast tego podam mój zwykły podział, a następnie bardziej szczegółowe wyjaśnienie, dlaczego kod działa.
Podział kodu
Wyjaśnienie
Kod najpierw wczytuje liczbę całkowitą do [0]. Każda iteracja głównej pętli (linie od 2 do 26) zwiększa się [1], a następnie kopiuje wszystko, co niezbędne, do algorytmu modułu, który wyrzuca wynik do [5]. Jeśli [5] zawiera dowolną wartość, to [1] jest liczbą, którą musimy wydrukować. Drukujemy go, a następnie wymuszamy zamknięcie programu.
Ponieważ COW jest pochodną od pieprzenia mózgu, działa względnie podobnie do tego, jak działa mózg - nieskończony pasek taśmy, możesz poruszać się w lewo lub w prawo, zwiększać lub zmniejszać oraz „zapętlać”, podczas gdy bieżąca wartość taśmy jest różna od zera. Oprócz pieprzenia mózgów, COW posiada kilka przydatnych funkcji.
Prawdziwym punktem zainteresowania jest tu instrukcja 3
mOO
. Interpreter odczytuje bieżącą wartość taśmy i wykonuje instrukcję na podstawie tej wartości taśmy. Jeśli wartość jest mniejsza niż 0, większa niż 11 lub równa 3, interpreter kończy program. Możemy użyć tego jako szybkiego i brudnego wyjścia z głównej pętli (i programu w całości) po znalezieniu naszego niepodzielnika. Wszystko, co musimy zrobić, to wydrukować nasz numer, wyczyścić [1] (zOOO
), zmniejszyć go do -1 za pomocąMOo
, a następnie wykonać instrukcję -1, za pomocąmOO
której program się kończy.Sama taśma dla tego programu działa w następujący sposób:
Algorytm modułu w naturalny sposób kasuje [2], [3], [6] i [7] pod koniec operacji. Zawartość [4] zostaje nadpisana pastą rejestru w wierszu 4, a [5] wynosi zero, gdy [0] jest podzielne przez [1], więc nie musimy go usuwać. Jeśli [5] jest niezerowe, wymuszamy wyjście z linii 23, więc nie musimy się o to martwić.
źródło
05AB1E , 7 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Galaretka , 5 bajtów
Wypróbuj online!
Wyjaśnienie:
To jest straszne nadużycie
#
; w tym programie jest wielu operatorów, ale mnóstwo brakujących operandów.#
naprawdę chce,1
aby z jakiegoś powodu podano je jawnie (w przeciwnym razie próbuje wejść domyślnie w dane wejściowe); jednak wszystko inne, co nie jest określone w programie, domyślnie przyjmuje dane wejściowe programu. (Na przykład, jeśli podasz 24 jako dane wejściowe, ten program znajdzie pierwsze 24 liczby, które nie dzielą 24, a następnie zwróci pierwszą; rodzaj marnotrawstwa, ale działa).źródło
2%@1#
C,
3235 bajtówEdycja: dodano
i=1
w pętliStosowanie
Pełna wersja programu, 64 bajty:
źródło
C #,
3937 bajtówZaoszczędź dwa bajty dzięki Martinowi!
źródło
Perl, 19 bajtów
18 bajtów kodu +
-p
flaga.Aby uruchomić:
Niezbyt szczegółowe wyjaśnienia:
-
$.
jest specjalną zmienną, której wartością domyślną jest bieżący numer wiersza ostatnio dostępnego uchwytu pliku (tutaj standardowe), więc po odczytaniu pierwszego wiersza wejścia, jest ustawiony na 1.-
$_
przechowuje dane wejściowe i jest domyślnie drukowany na końcu (dzięki-p
flagi).-
redo
(w tym kontekście) uważa, że program jest w pętli i ponownie wykonuje bieżącą iterację (tylko$.
będzie inna, ponieważ została zwiększona).- Więc jeśli znaleźliśmy najmniejszą liczbę (przechowywaną w
$.
), która się nie dzieli$_
, to ustawiamy$_
ją, w przeciwnym razie próbujemy następnej liczby (dziękiredo
).źródło
Octave / MATLAB,
2624 bajtówfind(...,1)
zwraca indeks (na podstawie1
) pierwszego niezerowego elementu wektora w pierwszym argumencie. Pierwszym argumentem jest[n mod 1, n mod 2, n mod 3, n mod 4,...,n mod (n+1)]
To, że musimy dodać+1
do indeksu, ponieważ zaczynamy testy od1
. Dzięki @Giuseppe za -2 bajty.Wypróbuj online!
źródło
@(n)find(mod(n,1:n+1),1)
jest krótszy, prawda?Galaretka , 6 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
[1, 1, 1, 1, 5, ...]
.Perl 6 , 17 bajtów
Spróbuj
Rozszerzony:
źródło
05AB1E , 6 bajtów
Wypróbuj online!
Napisuje też „LINK!” ... Trochę ...
źródło
Galaretka , 5 bajtów
Wypróbuj online!
Jak to działa
źródło
Python 2.7.9, 32 bajty
Testuj na Ideone
Rekurencyjnie liczy potencjalnych niepodzielników
d
. Krótsze jest rekurencyjne zwiększenie wyniku niż wyjścied
. Przesunięcie1
jest uzyskiwane przez wartość logicznąTrue
, która jest równa1
, ale ponieważd==1
zawsze jest dzielnikiem, wynik jest zawsze przekształcany na liczbę.Python 2.7.9 jest używany do zezwolenia
0or
. Wersje zaczynające się od 2.7.10 będą próbowały analizować0or
jako początek liczby ósemkowej i otrzymały błąd składniowy. Zobacz to w Ideone .źródło
Właściwie 7 bajtów
Wypróbuj online! (uwaga: jest to bardzo powolne rozwiązanie i zajmuje dużo czasu w przypadku dużych przypadków testowych)
Wyjaśnienie:
źródło
Haskell , 29 bajtów
Wyrażenie
[k|k<-[2..]]
tworzy po prostu nieskończoną listę[2,3,4,5,...]
. Pod warunkiemmod n k>0
dopuszczamy tylko te osobyk
z listy, które się nie dzieląn
. Dołączenie!!0
zwraca tylko pierwszy wpis (wpis o indeksie0
) z tej listy.Wypróbuj online!
źródło
Dyalog APL , 8 bajtów
1⍳⍨
pozycja pierwszego True w0≠
niezerowe wartości⍳|
pozostała część podziału 1 ... N po podzieleniu przez⊢
N.Wypróbuj APL online!
Uwaga: działa to dla 1 i 2, ponieważ
1⍳⍨
zwraca 1 + długość argumentu, jeśli nie zostanie znaleziony.źródło
Julia, 28 bajtów
Uwaga: ponieważ
1:N+2
nie przydziela pamięci, nie ma problemów z pamięcią dla dużychN
s- @flawr
N+2
zapisz dla mnie kilka bajtów- sugestia @Martin zapisała 1 bajt
źródło
QBIC , 14 bajtów
Wyjaśnienie:
źródło
PHP, 30 bajtów
jeśli uruchamiany z konsoli z
-r
opcją (thx do @ ais523)32 bajty
dzięki @manatwork za usunięcie 1 bajtu
33 bajty (oryginalne)
źródło
<?
nie musi być częścią twojej liczby bajtów (ponieważ PHP ma tryb wiersza poleceń, który tego nie wymaga).<1
zamiast==0
.for(;!($argv[1]%$i);$i++);echo$i;
. Twoja jest naturalną ewolucją mojej. To ma moje poparcie!Cubix ,
1412 bajtówZaoszczędź 2 bajty dzięki MickyT.
Spróbuj
Wyjaśnienie
W formie kostki kod to:
Zasadniczo wystarczy pobrać dane i uruchomić licznik. Następnie sprawdza każdą kolejną wartość licznika, aż znajdzie taką, która nie jest czynnikiem wejściowym.
źródło
I2/L/);?%<@O
za kilka bajtów mniej. Ten sam ogólny proces, po prostu inna ścieżka> <> , 15 +3 = 18 bajtów
Dane wejściowe powinny znajdować się na stosie podczas uruchamiania programu, więc +3 bajty dla
-v
flagi. Wypróbuj online!źródło
Meduza ,
1210 bajtówPobiera dane wejściowe ze STDIN i dane wyjściowe do STDOUT. Wypróbuj online!
Martin Ender zapisał 2 bajty, dzięki!
Wyjaśnienie
Ta część jest jedną funkcją, która wykorzystuje wartość wejściową w swojej definicji.
Ten
~
komórek beta otrzymuje funkcję, więc odwraca swoje argumenty: jej produkuje funkcję binarną „left modulo argument (|
) prawy argument”. Wbudowana funkcja modulo w meduzach przyjmuje argumenty w odwrotnej kolejności.Ten
~
komórek beta jest podana wartość i funkcję, więc robi częściowe zastosowanie: wytwarza binarny function „(wejściei
) Modulo prawy argument”. Nazwijmy tę funkcję f .\
Komórek beta otrzymuje dwie funkcje, a więc nie iteracji: wytwarza jednoargumentowych funkcja „(przyrost>
), aż funkcja f stosuje się do poprzedniego i prądu daje truthy (niezerowy) wynik, wtedy wartość prądu powrotu”. Oznacza to, że argument jest zwiększany, dopóki nie podzieli danych wejściowych.Na koniec zastosujemy tę funkcję do wartości początkowej
1
i wydrukujemy wynik za pomocąp
.źródło