# 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, 2017 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, 2018 at 4:41

# convey, 20 18 bytes

-2 thanks to Jo King!

 >!/|!!}
{"^."^[1


Try it online!

The values follow the arrow heads. { gets the N, here 24. This value is " duplicated and both values are then merged into !: repeat 24 for 24 times. The 24s go the right, while their indices are pushed down. Then index | 24 (mod) is calculated (for dividers this is 0). We repeat the corresponding index for i | 24 times, thus dividers get deleted. 5 on the other hand will be repeated 5 times. As we only want 1 of them, we take ! only 1 of them. The rest of the values build up and when nothing moves, the factory comes to a halt. Here is an ungolfed variant.

## ><>, 15 +3 = 18 bytes

1\n;
?\1+:{:}$%  Input is expected to be on the stack at program start, so +3 bytes for the -v flag. Try it online! ## Jellyfish, 12 10 bytes p\~~|1 >i  Takes input from STDIN and outputs to STDOUT. Try it online! Martin Ender saved 2 bytes, thanks! ## Explanation  \~~| >i  This part is one function that uses the input value in its definition.  ~|  This ~-cell is given a function, so it flips its arguments: its produces the binary function "left argument modulo (|) right argument". The built-in modulo function in Jellyfish takes its arguments in the reverse order.  ~~| i  This ~-cell is given a value and a function, so it does partial application: it produces the binary function "input (i) modulo right argument". Let's call that function f.  \~~| >i  The \-cell is given two functions, so it does iteration: it produces the unary function "increment (>) until the function f applied to previous and current values gives a truthy (nonzero) result, then return current value". This means that the argument is incremented until it doesn't divide the input. p\~~|1 >i  Finally, we apply this function to the initial value 1 and print the result with p. ## Pyke, 5 bytes 1D.f%  Try it here! 1D.f - first number after 1 where % - i%input != 0  # Beeswax, 19 bytes  >~P~q {~b"%g<~1fT_  Try it online! Example, using 3 as value  lstack gstack print _ [0,0,0] [] create bee T [0,0,3] enter number f [3] push top lstack value on gstack 1 [0,0,1] push 1 on lstack ~ [0,1,0] swap lstack 1st and 2nd g< [0,1,3] push gstack 1st on lstack % [0,1,0] lstack 1st = 1st % 2nd " if lstack 1st > 0 skip next, else don’t skip b redirect to upper left > redirect to right ~ [0,0,1] swap lstack 1st and 2nd P [0,0,2] increment lstack 1st ~ [0,2,0] swap lstack 1st and 2nd q redirect to lower right < redirect to left g [0,2,3] push gstack 1st on lstack % [0,2,1] lstack 1st = 1st % 2nd " lstack 1st > 0 → skip next ~ [0,1,2] swap lstack 1st and 2nd { "2" print lstack 1st to STDOUT end program  # Java 8, 44 + 2 = 46 bytes int m(int x,int y){return x%++y>0?y:m(x,y);}  Recursive solution which requires an extra ,1 when calling. Call with m(x,1). • Is the +2 for the parameter required? I use a recursive method as well sometimes, but usually I haven't included the parameter input (usually 0 or 1) in the byte-count. Is there a rule for this? Mar 24, 2017 at 8:35 • @KevinCruijssen It's outside of a standard call, so yes, I would consider it necessary. I do not know if there is any "rule" for this, but this is the fair-play method as far as I'm concerned. Mar 27, 2017 at 18:08 # Japt, 5 bytes @uX}a  Try it here # Ruby (C implementation), 26 bytes ->n{-(~n...0).min{|x|n%x}}  Explanation: ~n 2s-complement-bitwise-negates n, so it's equivalent for positive n to -(n+1). Let's work through with n=6. We generate a range from -7 to 0, excluding 0, and then find the minimum of that range using a custom comparison function. min expects a block that takes two arguments and returns a negative number if the first one is smaller, 0 if they're the same, and 1 if the first one is larger. Here, we're implicitly telling the block to ignore the second argument, so x is just the first element in the comparison. The block will return zero when x is the negation of a factor of n: in our n=6 example, 6%-3 is 0. When it's not, it'll be a negative number: 6%-4 is -2. So as Ruby iterates through the range, it'll do this: -7 is the first candidate for a minimum. Is -6 less than it? It passes -6 (x) and -7 (ignored) into the block, and the block returns 0 (since 6 is a factor of 6), so no. Is -5 less than it? It passes -5 in to the block and it returns a negative number, so yes. So the current candidate is -5. Is -4 less than -5? The block says yes. -3, -2, and -1 all get 0s, so -4 wins. Finally we negate the result to get 4. I'm calling this implementation-dependent since the Ruby spec would allow the sorting to be done differently, although my guess is most implementations do it this way. # TI-Basic, 17 bytes Absolutely genius to use the input as upper bound for for loop? For(I,1,Ans If not(fPart(Ans/I End I  • Ans is not an allowed I/O method. – user45941 Jan 9, 2017 at 18:47 • According to who? Jan 9, 2017 at 18:50 • That didn't work when I tested with 24. Jan 30, 2018 at 16:47 • @kamoroso94 Thanks for pointing that out, I had mistakenly put I/Ans instead of Ans/I but it's fixed now. Jan 31, 2018 at 4:11 # Husk, 5 bytes ←-NḊ  Try it online! The testing code prints the output for the first 100 terms. Note that the function runs in time proportional to the input value; the 1234567 case takes about 12 seconds on my machine. # Vyxalr, 5 bytes ?Ḋ¬)ṅ  Try it Online! Or # 5 bytes ₌ɾKFh  Try it Online! # Fig, $$\10\log_{256}(96)\approx\$$ 8.231 bytes [FJkxxG@}1  Try it online!  k # Get the factors of x # the input, J # then append x # the input to that (k doesn't include it). F # Filter out anything in that list from: G # an infinite list 1 # starting at 1 @} # incrementing each time. [ # Get the first item from that.  • Trailing xs can always be removed. Oct 13, 2022 at 4:08 • @Steffan Oh, true Oct 13, 2022 at 4:10 • "In particular, make sure that your answer works for inputs 1 and 2" Aug 7, 2023 at 11:49 • @DominicvanEssen Oops, missed that. Fixed now. Aug 7, 2023 at 21:40 # MATL, 6 bytes t:\f1)  Try it online! • You need Q after t so that it works for inputs 1 and 2 Jan 4, 2017 at 1:11 # Clojure, 48 Bytes (defn f[n](some #(if(>(mod n %)0)%)(range 1 n)))  # PowerShell, 26 bytes for(;!("$args"%++$i)){};$i


Try it online!

• Other solutions have switched from !() to <1, would that help here too?
– Neil
Jan 3, 2017 at 19:51
• @Neil powershell uses bash-style operators, so it would end up being -lt1 (or -eq0), one byte longer unfortunately. Jan 3, 2017 at 20:43

# Befunge, 2725 24 bytes

&:1>:00p%v
g1+^@.g00_:00


Try it online!

Explanation

&                 Read N from stdin.
:                Save a duplicate copy.
1               Push initial test divisor, D.

>              Main loop starts here.
:00p          Save a copy of the current D.
%v        Calculate N modulo D and move down.
_        If not zero (i.e. N is not divisible by D), then break to the left.
:       Otherwise continue to the right and prepare another copy of N.
g          00     Retrieve the previously saved D (wrapping to the beginning of the line).
1+               Increment D.
^              Repeat the loop again.

_        We break out of the loop going left.
g00         Retrieve the last value of D.
@.            Write it to stdout and exit.


Thanks to Mistah Figgins for saving me a byte.

• I believe you can shorten this by getting rid of the !. You would need to change the second line to g1+^@.g00_:00 (switching the direction of the 2 branches) Jan 3, 2017 at 19:01

# Retina, 28 bytes

.+
$*11 (1+?)(?!1\1*$).*
$.1  Try it online! Thanks to Martin for 6 bytes! In the first stage we generate N + 1 1s. Then we find the smallest number of ones such that we cannot fit that number evenly into N by hard-coding the offset by one that we introduced in the first step. This offsetting is used to allow 1 and 2 to work. ## Japt, 8 bytes U%°V?V:ß  This was inspired by Arnauld's solution. Thanks ETHproductions for golfing this even more! Try it Online! • I just realized that V defaults to 0, which allows you to do U%°V?V:ßUV (° is ++). Then you can take advantage of the fact that ß passes in U and V by default to do U%°V?V:ß for only 8 bytes :-) Jan 3, 2017 at 23:36 • @ETHproductions Wow, very nice! Jan 4, 2017 at 1:04 # REXX, 35 bytes arg a do n=1 until a//n>0 end say n  # dc, 21 bytes ?sn1[1+dlnr%0=b]dsbxp  Try it online! The program works by running through all integers starting with 2 until it finds one that isn't a divisor of the input. The input is kept in register n, and the current number being tested as a divisor/non-divisor is on the stack. Perl, 25 bytes sub{1 until$_[0]%++$i;$i}


# Ruby, 28 bytes

->n{(1..n+1).find{|x|n%x>0}}

• @GB yep, my bad. I foobed in the golfing stage. Jan 5, 2017 at 14:59

# S.I.L.O.S, 49 bytes

readIO
lbla
x+1
b=i
b%x
a=1
a-b
if a a
printInt x


Try it online!
Fairly simple. I was confused for a little while.

## Labyrinth, 13 bytes

+:#
" %#!
?:;


Try it online!

### Explanation

To avoid shifting around too many values to keep track of both the input and the current potential divisor, we're storing the latter implicitly as the stack depth by creating copies of the input. The 3x3 block on the left is the main loop. The first iteration doesn't really do anything, but it helps with the overall layout to delay reading the input until later.

+   Add top two stack elements. Does nothing on the first two iterations,
but removes a zero on subsequent iterations.
:   Duplicate. Does nothing on the first iteration, but copies the input
later on.
#   Push the stack depth. 2 on the first two iterations, increasingly larger
values later on.
%   Modulo. Gives zero on the first iteration, and acts as the trial division
later on. If this is positive, the loop is exited.
:   Duplicate a zero on the first iteration, the input on subsequent iterations,
increasing the stack depth.
?   Read input on first iteration, push zero later on.


Once % gives a positive value, we've found a non-divisor of the input. # pushes the stack depth once more, ! prints it. Then the IP hits a dead and turns around. Now #% will leave the top of the stack unchanged (and positive), so the IP now enters the 3x3 main loop in counter-clockwise order. #:+ pushes twice the stack depth but that's irrelevant. ?:; all together push a single zero so that the % now terminates the program due to a division by zero.

# Java 7, 54514947 46 bytes

Golfed:

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


Ungolfed:

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


Nothing fancy... I did try with a while(1>0) loop, was 2 bytes longer

• @Henry Pointed out in an attempted edit that you have extra whitespace in your if statement. It seems x % i > 0 can be replaced with x%i>0. Jan 4, 2017 at 4:27
• 47 bytes: int n(int x){int y=1;for(;x%++y==0;);return y;} Jan 4, 2017 at 10:13
• For future reference (it doesn't really help here, but still), you don't need the for-loop brackets when using a single if statement followed by a function (so for(;;)if(true)x(); would work), and you can use for(;;) instead of while(1>0). Jan 4, 2017 at 10:20
• @peech You can use my solution in the comment two above this, you know. ;) Shaves off another two bytes. Jan 4, 2017 at 16:17
• instead i==0 write i<1 Jan 7, 2017 at 13:12

# SmileBASIC, 46 bytes

INPUT N
FOR I=2TO N+1
IF N MOD I THEN ?I:Q
NEXT


I hope that triggering an error to end the program is allowed.

# Emojicode, 74 bytes

🐖🔢➡️🚂🍇🍮i 1🔁😛0🚮🐕i🍇🍮i➕1i🍉🍎i🍉


Try it online!

# C (gcc) 30 bytes

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


Try it online!

# Forth (gforth), 31 bytes

: f 1 begin 1+ 2dup mod until ;


Try it online!

### Explanation

 1        \ place a 1 on the stack (divisor)
begin    \ start an indefinite loop
1+       \ add 1 to the divisor
2dup     \ duplicate the top 2 stack items (n and divisor)
mod      \ get n%divisor and place it on top of the stack
until    \ end the loop when the top of the stack is anything other than 0


# ><>, 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.