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

Mathematica, 19 bajtów (kodowanie UTF-8)

1//.x_/;x∣#:>x+1&

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:

1                   Starting with 1,
 //.                apply the following rule until it stops mattering:
    x_                if you see a number x
      /;x∣#           such that x divides the function argument,
           :>x+1      replace it with x+1.
                &   Cool, that's a function.

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//.yz ReplaceRepeated[x,y,MaxIterations->∞]naprawić tę wadę, ale oczywiście kosztem 34 dodatkowych bajtów.

Pyth, 3 bajty

f%Q

Zasadniczo fzapętla kod, dopóki %QT( Q % Tgdzie Tjest zmienna iteracyjna) nie będzie prawdą.

Wypróbuj online tutaj.

JavaScript (ES6), 25 23 bajtów

f=(n,k)=>n%k?k:f(n,-~k)

Uwaga: Jedną interesującą rzeczą jest to, że kparametr jest inicjowany ex nihilo przy pierwszej iteracji. Działa n % undefinedto, ponieważ jest NaN(fałsz zgodnie z oczekiwaniami) i -~undefinedrówna się 1. W następnych iteracjach -~kjest zasadniczo równoważny z k+1.

Test

f=(n,k)=>n%k?k:f(n,-~k)

// first 100 terms
for(i = 1, list = []; i <= 100; i++) {
  list.push(f(i));
}
console.log(list.join(' '));

// larger test cases
console.log(f(1234567));
console.log(f(12252240));
console.log(f(232792560));

Python, 43 36 35 bajtów

f=lambda n,d=2:d*(n%d>0)or f(n,d+1)

Sześciokąt , 12 bajtów

\\)?}'@{!%.}

Embiggened:

   \ \ )
  ? } ' @
 { ! % . }
  . . . .
   . . .

Wypróbuj online!

R, 28 bajtów

Całkiem proste, nic szczególnego. Pobiera dane wejściowe ze stdin, zwiększa wartość, Taż imodulo Tjest niezerowe.

i=scan()
while(!i%%T)T=T+1
T

Jeśli chcesz czegoś bardziej fantazyjnego, na 29 bajtów są następujące :

i=scan()
match(0,!i%%1:(i+1))

Wyjaśniono:

i=scan(): Przeczytaj ize standardowego.

1:(i+1): Wygeneruj wszystkie liczby całkowite od 1do i+1( +1uwzględniające przypadki 1i 2).

i%%1:(i+1) : Zmoduluj dane wejściowe według każdej liczby z naszej listy.

!i%%1:(i+1): Neguj wynikową listę; to niejawnie konwertuje go do typu logicznego, tak że 0jest FALSEi jest różna od zera TRUE. Po zanegowaniu TRUEwartości stają się FALSEi na odwrót. Teraz wszystkie pierwotnie niezerowe wartości są kodowane jako FALSE.

match(0,!i%%1:(i+1)): Zwraca indeks pierwszego wystąpienia 0na naszej liście. 0jest FALSE, więc zwraca indeks pierwszego FALSEna liście, który jest pierwszą niezerową wartością z operacji modulo. Od początku naszej oryginalnej listy 1indeks jest równy wartości najmniejszego niepodzielnika.

Haskell, 26 bajtów

f n=until((>0).mod n)(+1)1

Każdy zapomina o until!

Brachylog , 10 bajtów

~{=#>:A'*}

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:

~{=#>:A'*}
~{       }    inverse of the following function:
  =           try possible values for the input, if it's unbound
   #>         the input is a positive integer
     :A'*     there is no A for which the input times A is the output

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.

Brachylog , 11 10 bajtów

,.=:?r'%0'

Wypróbuj online!

Wyjaśnienie

,.=           Assign an integer to the output
 . :?r'%0     Input mod Output ≠ 0
        0'    Output ≠ 0

COW, 174 bajty

oomMOOMMMmoOmoOmoOMMMmOomOoMoOMMMmoOmoOmoOMMMmOoMOOmoO
MOomoOMoOmOoMOOmoOmoomoOMOOmOoMoOmoOMOomoomOomOoMOOmOo
moomoOMOomoomoOmoOMOOmOomOomOomOoOOMOOOMOomOOmoomOomOo
mOomOomOomoo

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

oom                          ;Read input into [0].
MOO                          ;Loop while [0].  We never change [0], so the program only terminates forcibly after a print.
  MMMmoOmoOmoOMMMmOomOo      ; Copy [0] to [3] and navigate to [1].
  MoOMMMmoOmoOmoOMMM         ; Increment [1], and copy it to [4]
  mOo                        ; Navigate back to [3].
  MOO                        ; Modulus algorithm.  Direct port of brainfuck algorithm.
    moOMOomoOMoOmOo
    MOO
      moO
    moo
    moO
    MOO
      mOoMoOmoOMOo
    moo
    mOomOo
    MOO
      mOo
    moo
    moOMOo
  moo                        ; End modulus algorithm.
  moOmoO                     ; Navigate to [5].  This contains our modulus.
  MOO                        ; Only perform these operations if [5] is non-zero -- i.e. [0] % [1] != 0
    mOomOomOomOoOOMOOOMOomOO ;  Navigate to [1], print its contents, then error out.
  moo                        ; End condition
  mOomOomOomOomOo            ; Since we're still running, [0] % [1] == 0, so navigate back to [0] and try again.
moo                          ;End main loop.

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.

(0) moo -- Equivalent to ]
(1) mOo -- Equivalent to <
(2) moO -- Equivalent to >
(3) mOO -- No equivalent.  Evaluate current tape value as instruction from this list.
(4) Moo -- If tape is 0, equivalent to ,; if tape is non-zero, equivalent to .
(5) MOo -- Equivalent to -
(6) MoO -- Equivalent to +
(7) MOO -- Equivalent to [
(8) OOO -- No equivalent.  Set tape (positive or negative) to 0
(9) MMM -- No equivalent.  If register is empty, copy tape to register.  If register is non-empty, paste register to tape and clear register.
(10) OOM -- No equivalent.  Print an integer from tape to STDOUT
(11) oom -- No equivalent.  Read an integer from STDIN and store it on tape

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] (z OOO), zmniejszyć go do -1 za pomocą MOo, a następnie wykonać instrukcję -1, za pomocą mOOktórej program się kończy.

Sama taśma dla tego programu działa w następujący sposób:

[0]  -- Read-in integer from STDIN.
[1]  -- Current divisor to test
[2]  -- Placeholder for modulus algorithm
[3]  -- Temporary copy of [0] for use for modulus algorithm
[4]  -- Temporary copy of [1] for use for modulus algorithm
[5]  -- Placeholder for modulus algorithm.  Location of remainder at end of loop.
[6]  -- Placeholder for modulus algorithm
[7]  -- Placeholder for modulus algorithm

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ć.

05AB1E , 7 bajtów

Xµ¹NÖ_½

Wypróbuj online!

Wyjaśnienie

Xµ       # run until counter is 1
  ¹      # push input
   N     # push iteration counter
    Ö_   # push input % iteration counter != 0
      ½  # if true, increase counter
         # output last iteration

Galaretka , 5 bajtów

1%@#Ḣ

Wypróbuj online!

Wyjaśnienie:

1%@#Ḣ
1  #      Find the first … numbers, counting up from 1, such that
 %@       dividing those numbers into … gives a truthy remainder
    Ḣ     then return the first

To jest straszne nadużycie #; w tym programie jest wielu operatorów, ale mnóstwo brakujących operandów. #naprawdę chce, 1aby 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).

C, 32 35 bajtów

i;f(x){for(i=1;x%++i<1;);return i;}

Edycja: dodano i=1w pętli

Stosowanie

main(c,v)char**v;{printf("%d",f(atoi(*++v)));}

Pełna wersja programu, 64 bajty:

main(c,v)char**v;{*++v;for(c=1;atoi(*v)%++c<1;);printf("%d",c);}

C #, 39 37 bajtów

n=>{int i=0;while(n%++i<1);return i;}

Zaoszczędź dwa bajty dzięki Martinowi!

Perl, 19 bajtów

18 bajtów kodu + -pflaga.

$_=$_%++$.?$.:redo

Aby uruchomić:

perl -pE '$_=$_%++$.?$.:redo' <<< 12252240

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 -pflagi).
- 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ęki redo).

Octave / MATLAB, 26 24 bajtów

@(n)find(mod(n,1:n+1),1)

find(...,1)zwraca indeks (na podstawie 1) 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ć +1do indeksu, ponieważ zaczynamy testy od 1. Dzięki @Giuseppe za -2 bajty.

Wypróbuj online!

Galaretka , 6 bajtów

%R;‘TḢ

Wypróbuj online!

Wyjaśnienie:

                                               Assume 24 is our N
 R      Generate all numbers from 1 to N         [1, 2, 3, 4 .., 24]
  ;‘    Attach N+1 to that list (for cases 1,2)  [1, 2, 3, 4 .., 25]
%       And modulo-divide our input by it
        Yields a list with the remainder         [0, 0, 0, 0, 4 ...]
    T   Return all thruthy indexes               [5, 7, ...]
     Ḣ  Takes the first element of that list -->  5

Perl 6 , 17 bajtów

{first $_%*,1..*}

Spróbuj

Rozszerzony:

{  # bare block lambda with implicit parameter ｢$_｣

  # return the first value
  first

  # where the block's argument ｢$_｣ modulus the current value ｢*｣
  # doesn't return 0 ( WhateverCode lambda )
  $_ % *,
  # ( ｢$_ !%% *｣ would be the right way to write it )

  # from 1 to Whatever
  1 .. *
}

05AB1E , 6 bajtów

ÌL¹ÑK¬

Wypróbuj online!

Napisuje też „LINK!” ... Trochę ...

ÌL     # Push [1..n+2]
  ¹Ñ   # Push divisors of n.
    K¬ # Push a without characters of b, and take first item.

Galaretka , 5 bajtów

‘ḍ€i0

Wypróbuj online!

Jak to działa

‘ḍ€i0  Main link. Argument: n

‘      Increment; yield n+1.
 ḍ€    Divisible each; test 1, ..., n+1 for divisibility by n.
   i0  Find the first index of 0.

Python 2.7.9, 32 bajty

f=lambda n,d=1:n%d>0or-~f(n,d+1)

Testuj na Ideone

Rekurencyjnie liczy potencjalnych niepodzielników d. Krótsze jest rekurencyjne zwiększenie wyniku niż wyjście d. Przesunięcie 1jest uzyskiwane przez wartość logiczną True, która jest równa 1, ale ponieważ d==1zawsze 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ć 0orjako początek liczby ósemkowej i otrzymały błąd składniowy. Zobacz to w Ideone .

Właściwie 7 bajtów

;÷@uR-m

Wypróbuj online! (uwaga: jest to bardzo powolne rozwiązanie i zajmuje dużo czasu w przypadku dużych przypadków testowych)

Wyjaśnienie:

;÷@uR-m
;÷       duplicate N, divisors
  @uR    range(1, N+2)
     -   set difference (values in [1, N+1] that are not divisors of N)
      m  minimum

Haskell , 29 bajtów

f n=[k|k<-[2..],mod n k>0]!!0

Wyrażenie [k|k<-[2..]]tworzy po prostu nieskończoną listę [2,3,4,5,...]. Pod warunkiem mod n k>0dopuszczamy tylko te osoby kz listy, które się nie dzielą n. Dołączenie !!0zwraca tylko pierwszy wpis (wpis o indeksie 0) z tej listy.

Wypróbuj online!

Dyalog APL , 8 bajtów

1⍳⍨0≠⍳|⊢

1⍳⍨ pozycja pierwszego True w

0≠ 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.

Julia, 28 bajtów

N->findfirst(x->N%x>0,1:N+2)

Uwaga: ponieważ 1:N+2nie przydziela pamięci, nie ma problemów z pamięcią dla dużych Ns
- @flawr N+2zapisz dla mnie kilka bajtów
- sugestia @Martin zapisała 1 bajt

QBIC , 14 bajtów

:[a+1|~a%b|_Xb

Wyjaśnienie:

:      Read the first cmd line param as a number, called 'a'
[a+1|  FOR (b=1 ; b <= a+1; b++) <-- a+1 for cases a = 1 or 2
~a%b   IF A modulo B ( == 0, implicit)
|_Xb   THEN exit the program, printing b
       [IF and FOR implicitly closed by QBIC]

PHP, 30 bajtów

for(;$argv[1]%++$i<1;);echo$i;

jeśli uruchamiany z konsoli z -ropcją (thx do @ ais523)

php -r 'for(;$argv[1]%++$i<1;);echo$i;' 232792560

32 bajty

<?for(;$argv[1]%++$i<1;);echo$i;

dzięki @manatwork za usunięcie 1 bajtu

33 bajty (oryginalne)

<?for(;$argv[1]%++$i==0;);echo$i;

Cubix , 14 12 bajtów

I2/L/);?%<@O

Zaoszczędź 2 bajty dzięki MickyT.

Spróbuj

Wyjaśnienie

W formie kostki kod to:

    I 2
    / L
/ ) ; ? % < @ O
. . . . . . . .
    . .
    . .

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.

> <> , 15 +3 = 18 bajtów

1\n;
?\1+:{:}$%

Dane wejściowe powinny znajdować się na stosie podczas uruchamiania programu, więc +3 bajty dla -vflagi. Wypróbuj online!

Meduza , 12 10 bajtów

p\~~|1
 >i

Pobiera dane wejściowe ze STDIN i dane wyjściowe do STDOUT. Wypróbuj online!

Martin Ender zapisał 2 bajty, dzięki!

Wyjaśnienie

 \~~|
 >i

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.

  ~~|
  i

Ten ~komórek beta jest podana wartość i funkcję, więc robi częściowe zastosowanie: wytwarza binarny function „(wejście i) Modulo prawy argument”. Nazwijmy tę funkcję f .

 \~~|
 >i

\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.

p\~~|1
 >i

Na koniec zastosujemy tę funkcję do wartości początkowej 1i wydrukujemy wynik za pomocą p.