Find the smallest number that doesn't divide N

This challenge is simple enough that it's basically all in the title: you're given a positive integer N and you should return the smallest positive integer which is not a divisor of N.

An example: the divisors of N = 24 are 1, 2, 3, 4, 6, 8, 12, 24. The smallest positive integer which is not in that list is 5, so that's the result your solution should find.

This is OEIS sequence A007978.

Rules

You may write a program or a function and use any of the our standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

Test Cases

The first 100 terms are:

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


In particular, make sure that your answer works for inputs 1 and 2 in which case the result is larger than the input.

And for some larger test cases:

N          f(N)
1234567    2
12252240   19
232792560  23


Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 105412; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});

});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();

languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• I turned the sample output string into a vector of numbers, and realized that if you format it 24 columns across, it's extremely repetitive, except for the odd deviation. Jan 6 '17 at 0:05
• That makes sense, 24 is 0 mod 2, 3, and 4, so the only differences would be in columns where the numbers are >4. It's even more repetitive at width 120. Jan 31 '18 at 4:41

GolfScript, 15 bytes

~:x;1{).x\%!}do


Try it online!

~:x;              # Store the input in the variable x
1             # Push 1
{     !}do   # While it is zero
)           # Go to the next number
.x\%       # x mod the current number


Python 3, 39 bytes

f=lambda x,i=1:i if x%i!=0else f(x,i+1)


Try it online!

This function just returns the second argument if it's a valid answer, and calls itself with an incremented second argument otherwise.

• Welcome to the site, and nice first answer! I've edited in a link to an online testing environment so that others can test and run your code. You can save 2 bytes by removing the !=0 (Try it online!) and be sure to check out our Tips for golfing in Python page for more ways you could golf your answer. Jan 28 '21 at 11:08
• I got it down to 36, but how is left as an exercise to the reader ;) Feb 1 '21 at 23:49

C 70 bytes

 s(int *n){ int f=1;for(f=1;f<(*n);f++){if((*n)%f!=0)return f;}return f;}


Racket 52 bytes

(let p((n 2))(cond[(= 0(modulo m n))(p(+ 1 n))][n]))


Ungolfed:

(define (f m)
(let loop ((n 2))
(cond
[(= 0 (modulo m n))
(loop (+ 1 n))]
[else n])))


Testing:

(f 24)
(f 1234567)
(f 12252240)
(f 232792560)


Output:

5
2
19
23


bash, 37 bytes

(($1%${2-1}))&&echo $2||$0 $1$[$2+1]  Save the program in a file. Run it from the command line with the input number N as an argument: scriptname N • (($1%($2)))&&bc<<<$2||$0$1 $2+1 to be run as scriptname N 2 Jan 7 '17 at 7:35 • @izabera I like the idea of using bc, but I can't get it to be any shorter than the original 37 bytes without the contrivance of passing the extra argument 2. Jan 7 '17 at 18:04 Batch, 53 bytes @set/ad=%2+1,r=%1%%d @if %r%==0 %0 %1 %d% @echo %d%  Well I beat Java anyway... Explanation: • set /a d = %2 + 1 This takes the second argument and adds 1. Of course, normally there is no second argument, but that's no problem, you just get +1, which is still a legal expression. • set /a r = %1 %% d Since % is the argument/variable modifier, we need to double it to flag it as the remainder operator. • %0 %1 %d% This is a form of tail recursion. %0 refers to the batch file itself, %1 is the original parameter and %d% is our loop variable, becoming %2 in the next iteration. FALSE, 32 bytes This FALSE solution is similar to the DUP solution because DUP is a dialect of FALSE with some extra abilities. 1[[$@@@@\/*-0=][1+]#.]a:\a;!  In contrast to DUP, FALSE lacks the convenient MOD,DIV operator that computes both the MOD and DIV of two numbers at one time. FALSE only offers an integer division operator /. FALSE also does not offer the convenient OVER operator, and using the PICK 1ø operator combo instead costs 3 bytes each. So, the solution above is actually the cheapest way to implement the OVER and MOD operators in FALSE. Insert the value to be tested between the : and the \, like this: 1[[$@$@$@$@\/*-0=][1+]#.]a:1234567\a;!


Explanation:

1[[$@@@@\/*-0=][1+]#.]a:n\a;! (n marks the number) 1 [1] PUSH 1 (counter c) [ ]a: define function a n [1,n] PUSH n \ [n,1] SWAP a;! fetch address of a, execute a [ ][ ]# while loop while 1st block true, execute 2nd block \ ~1~ [1,n] SWAP  DUP @ ROT @@@ [n,1,n,1,n,1] DUP,ROT,DUP,ROT,DUP,ROT,SWAP (create 2 duplicates of the pair) / [n,1,n,1,n/1=n] DIV * [n,1,n,1*n] MUL - [n,1,n-n=0] SUB 0 [n,1,0,0] PUSH 0 = [n,1,-1] if 0==0 PUSH true(-1), else push false (0) if true, execute next block, if false, continue at ~2~ ] [1+]# [n,2] PUSH 1, ADD, (increment c), loop back to ~1~ . ~2~ [n,c] print integer c (top stack value) to STDOUT  Try it out here. • You can remove the function definition/call entirely: 1[$@$@$@$@\/*-0=][1+]#. to get 24 bytes. (insert the value to test at the beginning) Jan 30 '18 at 15:39 DUP, 23 bytes (21 chars) DUP is a derivative of FALSE, with a similar solution. 1[[^^/%0=][1+]#.]⇒a\a  Insert the value to be tested between the first a and the \, like this: 1[[^^/%0=][1+]#.]⇒a1234567\a  Explanation:  data stack 1 [1] PUSH 1 on data stack [ ]⇒a define operator a n [1,n] PUSH integer n on data stack \ [n,1] SWAP a execute operator a 1[[^^/%0=][1+]#.]⇒a1234567\a [ ][ ]# while loop: while first block true, execute second block [ ~1~ ^ [n,1,n] OVER ^ [n,1,n,1] OVER / [n,1,n%1,n/1] MODDIV: computes mod and division % [n,1,n%1] POP 0 [n,1,n%1,0] PUSH 0 = [n,1,true/false] n%1 == 0 ? ] if false (0), continue at ~2~ if true (-1), execute next block [ 1 [n,1,1] PUSH 1 + [n,2] ADD ]# return to ~1~ . ~2~ [n] print number to STDOUT exit operator a, end program  Try it out here. Or clone my DUP GitHub repository for a DUP interpreter written in Julia, with full documentation. Matlab, 45 Bytes function x=n(a) x=2;while(~mod(a,x))x=x+1;end  Vitsy, 17 bytes V2v[VvDD1+v{M(x&]  The output is the exit code of this program. Assuming that less that LCM(Range(1,128)) is acceptable range. Try it online! Explanation: Let [...] at the end of the line signify the state of the stack at that line. V2v[VvDD1+v{M(x&] V Capture the input as a final global variable (FGV). 2v Save 2 as a temporary variable. [ ] Repeat the item in brackets forever. V Push the FGV to the stack. v Dump the temporary variable (TV) to the stack. (call it "x") DD Duplicate twice. The stack looks like [FGV, x, x, x]. 1+ Add one to the top value. [FGV, x, x, x+1] v Capture the top value as the new temp var. (TV = x+1) [FGV, x, x] { Rotate the top to the bottom of the stack. [x, FGV, x] M Pop the top two values, push second-to-top mod top. [x, FGV%x] ( Pop the top value. If it is zero, then... [x] x Pop the top value and exit with that exit code. [] & Enter a new stack. (Reset the stack).  Java 8, 37 bytes n->{int i=1;while(n%++i<1);return i;}  Scala, 33 bytes (n:Int)=>(1 to n+1)find(n%_>0)get  Straightforwardly constructs a Range that covers the possible answers, finds the first one that is an answer, and gets it from the Option, knowing that it must exist. C++ 55 Bytes start: while(n%i>0) {;goto end;} i++; goto start; end:;  The while loop checks whether the number(input given by the user) is divisible by i(here the divisor which is continuously increasing). The entire code is #include<iostream> using namespace std; int main(){ int n,i=1; cout<<"Enter A Number"; cin>>n; start: while(n%i>0) { cout<<"The lowest integer that does not divide "<<n<<" is "<<i; goto end; } i++; goto start; end: return 0; }  • You don't need all that whitespace, and you can easily save bytes by using shorter identifiers than end and start. On the other hand, you do need to submit either a full program or a function (not a snippet, like you have there), and you current demonstration code is way too long to really serve that role. (I also think you're using rather more verbose control constructs than you need to; in the C family, for is normally best for loops in code-golf because it's fairly flexible and it has the shortest name.) – user62131 Jan 5 '17 at 8:12 Q/KDB+ 36 Bytes f:{$[0=(y%x)mod 1;f[x+1;y];x]}
f[1;n]


Description:
Function f

f:{$[0=(y%x)mod 1;f[x+1;y];x]}  which consists of a conditional $[0=(y%x)mod 1;f[x+1;y];x]


The conditional has 3 statements, each separated by a semi colon.

0=(y%x)mod 1  //y divided by x, mod 1 to determine if it is a decimal or not.
f[x+1;y]      //If it is not a decimal, call the function again and increment x.
x             //If it is a decimal, return x (as it doesn't divide n evenly.


To call the function:

f[1;n]


Start at 1 and pass in the value of n.

GameMaker Language, 58 bytes

a=argument0 for(i=1;i<=a;i++){if a mod i return i}return i


Clojure, 90 bytes

Horribly long, but I like how it reads ungolfed.

#(apply min(remove(into #{}(filter(fn[m](=(rem % m)0))(range 1(+ % 1))))(range 2(+ % 2))))


I probably have a lot of room to golf this given this was a totally naïve attempt at an algorithm.

Ungolfed:

(defn smallest [n]
(let [mults (into #{} (filter (fn [m] (= (rem n m) 0)) (range 1 (+ n 1))))] ; Find multiples, and place in a set for membership lookup
(apply min ; Find minimum non-multiple
(remove mults ; Remove multiples from the range 2 to (n+2)
(range 2 (+ n 2))))))


C (gcc) 30 bytes

i;f(n){for(i=0;n%++i<1;);i=i;}


Try it online!

FALSE, 2219 18 bytes

1[$$3ø\/*2ø=][1+]#  This is a modified version of the other FALSE answer (which is itself a modified version of the DUP answer) 1[[$@@@@\/*-0=][1+]#.]a:\a;!  First, of course, we can remove that function definition/call, as well as outputting the number to the stack instead of printing: 1[$@@@@\/*-0=][1+]#  $@@@@\ is used to create 2 copies of the top 2 values on the stack {a,b} -> {a,b,a,b,a,b}. This can be shortened to 1ø1ø1ø1ø or 2ø$2ø\ 1[2ø$2ø\/*-0=][1+]#  For some reason, they are using a-b==0 rather than just a==b... 1[2ø$2ø\/*=][1+]#  And then I messed around some more to save 1 character: 1[$$3ø\/*2ø=][1+]#


Julia 0.6, 25 bytes

f(n,x=2)=n%x>0?x:f(n,x+1)


Try it online!

L,RqVAFB]qG$_bUm  Try it online! How it works L, ; Create a lambda function ; Example argument: [24] R ; Range; [[1 2 3 4 ... 22 23 24]] q ; Set; [{1 2 3 4 ... 22 23 24}] V ; Save and pop; [] AFB]q ; Push the factors; [{1 2 3 4 6 8 12 24}] G ; Retrieve; [{1 2 3 4 6 8 12 24} {1 2 3 ... 22 23 24}]$_h	; Set difference;   [{5 7 9 ... 22 23 24}]
bUm	; Minimum;          5


Jelly, 6 bytes

R‘ḟÆDḢ


Try it online!

Explanation:

R‘ḟÆDḢ Example input: 5
R      Range 1 to implicit input. [1,2,3,4,5]
‘     Increment. [2,3,4,5,6]
ḟ    Filter out...
ÆD  The divisors. [2,3,4,6]
Ḣ Get the first one. 2
Implicit output


><>, 12 + 3 = 15 bytes

:l%?v:
;nll<


Try it online!

Takes input via the -v flag. Uses the length of the stack as a counter to check the divisibility of the number.

SNOBOL4 (CSNOBOL4), 57 bytes

F	F =F + 1
GT(REMDR(N,F))	:S(RETURN)F(F)
DEFINE('F(N)')


Try it online!

Funky, 28 bytes

n=>fori=1i<n i++ifn%i breaki


Obvious solution, but also short enough for me.

Might be the first time I've used break instead of return competitively.

Try it online!

Pyt, 11 bytes

Đ⁺ř|¬ĐŁř*ž↓


Explanation:

                       Implicitly takes input
Đ                      Duplicates input
⁺                     Increments by 1
ř                    Push [1,2,...,input+1]
|¬                  Does each of [1,2,...,input+1] not divide the input
Đ                 Duplicate the array
Ł                Get the length
ř               Push [1,2,...,length]
*              Multiply the top two array elementwise
ž             Remove all zeroes
↓            Get the minimum
Implicit print


Try it online!

Whitespace, 58 bytes

[S S S T    N
_Push_1][S N
S _Dupe_1][S N
S _Dupe_1][T    N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][S N
T   _Swap][N
S S N
_Create_Label_LOOP][S S S T N
_Push_1][T  S S S _Add][S T S S T   N
_Copy_0-based_1st_input][S T    S S T   N
_Copy_0-based_1st_n][T  S T T   _Modulo][N
T   S N
_If_0_Jump_to_Label_LOOP][T N
S T _Print_as_integer]


Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer input = STDIN as integer
Integer n = 1
Start LOOP:
n = n + 1
If(input modulo n == 0):
Go to next iteration of LOOP
Print n as integer to STDOUT
(Implicitly terminate the program with an error because no exit is defined)


Example program flow (input 24):

Command  Explanation                   Stack        Heap      STDIN  STDOUT  STDERR

SSSN     Push 1                        [1]
SNS      Duplicate 1                   [1,1]
SNS      Duplicate 1                   [1,1,1]
TNTT     Read STDIN as integer         [1,1]        [{1:24}]  24
TTT      Retrieve from heap #1         [1,24]       [{1:24}]
SNT      Swap top two                  [24,1]       [{1:24}]
NSSN     Create Label LOOP             [24,1]       [{1:24}]
SSSTN     Push 1                       [24,1,1]     [{1:24}]
TSSS      Add top two (1+1)            [24,2]       [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,2,24]    [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,2,24,2]  [{1:24}]
TSTT      Modulo (24%2)                [24,2,0]     [{1:24}]

SSSTN     Push 1                       [24,2,1]     [{1:24}]
TSSS      Add top two (2+1)            [24,3]       [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,3,24]    [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,3,24,3]  [{1:24}]
TSTT      Modulo (24%3)                [24,3,0]     [{1:24}]

SSSTN     Push 1                       [24,3,1]     [{1:24}]
TSSS      Add top two (3+1)            [24,4]       [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,4,24]    [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,4,24,4]  [{1:24}]
TSTT      Modulo (24%4)                [24,4,0]     [{1:24}]

SSSTN     Push 1                       [24,4,1]     [{1:24}]
TSSS      Add top two (4+1)            [24,5]       [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,5,24]    [{1:24}]
STSSTN    Copy (0-based) 1st from top  [24,5,24,5]  [{1:24}]
TSTT      Modulo (24%5)                [24,5,4]     [{1:24}]

TNST      Print as integer             [24]         [{1:24}]         5
error

• @Grimmy Thanks and nice fix. I knew I could fix it by adding a +2, but then it would have the same 6 bytes as the other 05AB1E answer, which is why I deleted it. But using an infinite list is a smart alternative to fix, at the cost of no additional bytes. :) Jan 22 '20 at 14:07

Whd, 7 5 bytes

W is doing pretty great, given its lack of a break-out-of-loop instruction!

▲²!░╠


Explanation

% Since W doesn't support breaking out
% of loops based on a condition, (design
% preference: I don't like while loops):
% We need some reasoning. We know that
% n and n+1 are always coprime with
% each other, so why not generate a
% range from 1 to n+1?
1+       % Add the inplicit input by 1
W   % Generate range from 1 to input + 1
% Keep everything that
% fullfills the following condition
bam    % b%a is not falsy (sorry, implicit input
% isn't working properly)
% Here, b is the input and a is the current item.

Flag:h % Output the first item of the output
$$$$


function f($n){do{$y++;$d=$n%$y}while($d-eq0)$y}  Edited to be a function. I'm not really sure how I would golf the "function" bit, but I'm sure there's a way. • Welcome to PPCG! This is a good first answer, but I think you are assuming that the input is in a variable called n. That is not allowed, because we have some standard Input / Output methods. I think you could modify your code (currently a snippet) to make it either a function, or a full program accepting input from STDIN / Command Line Arguments. I might be wrong, since I don't know Powershell :) Jan 31 '18 at 18:09 Perl 5-p, 15 bytes 1until$_%++\$\}{


Try it online!

Brachylog v2, 5 bytes

f≡ⁿℕ₁


Try it online!

   ℕ₁    The output is a positive integer
≡ⁿ      which is not an element of
f        the input's factors.
`