# Definition

A number is positive if it is greater than zero.

A number (A) is the divisor of another number (B) if A can divide B with no remainder.

For example, 2 is a divisor of 6 because 2 can divide 6 with no remainder.

# Goal

Your task is to write a program/function that takes a positive number and then find all of its divisors.

# Restriction

• You may not use any built-in related to prime or factorization.
• The complexity of your algorithm must not exceed O(sqrt(n)).

# Freedom

• The output list may contain duplicates.
• The output list does not need to be sorted.

# Scoring

This is . Shortest solution in bytes wins.

# Testcases

input    output
1        1
2        1,2
6        1,2,3,6
9        1,3,9

• You probably mean divisor, not factor. And I guess you want to have a time complexity of O(sqrt(n)). Commented May 1, 2016 at 8:40
• What is the difference between divisor and factor? Commented May 1, 2016 at 8:42
• We talk about factors of e.g. a number, if the product of these results in the original number again, but the divisors are usually the numbers that divide said number without remainder. Commented May 1, 2016 at 8:44
• @flawr Updated accordingly. Commented May 1, 2016 at 8:45
• Should have more examples. 99 (1 3 9 11 33 99) Commented May 1, 2016 at 18:53

# PostgreSQL, 176 bytes

WITH c AS(SELECT * FROM(SELECT 6v)t,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT string_agg(r::text,',' ORDER BY r)
FROM(SELECT r FROM c UNION SELECT v/r FROM c)s


SqlFiddleDemo

Input: (SELECT ...v)

How it works:

• (SELECT ...v) - input
• generate_series(1, sqrt(v)::int) - numbers from 1 to sqrt(n)
• WHERE v%r=0 -filter divisors
• wrap with common table expression to refer twice
• SELECT r FROM c UNION SELECT v/r FROM c generete rest of divisors and combine
• SELECT string_agg(r::text,',' ORDER BY r) produce final comma separated result

Input as table:

WITH c AS(SELECT * FROM i,generate_series(1,sqrt(v)::int)s(r)WHERE v%r=0)
SELECT v,string_agg(r::text,',' ORDER BY r)
FROM(SELECT v,r FROM c UNION SELECT v,v/r FROM c)s
GROUP BY v


SqlFiddleDemo

Output:

╔═════╦════════════════╗
║ v   ║   string_agg   ║
╠═════╬════════════════╣
║  1  ║ 1              ║
║  2  ║ 1,2            ║
║  6  ║ 1,2,3,6        ║
║  9  ║ 1,3,9          ║
║ 99  ║ 1,3,9,11,33,99 ║
╚═════╩════════════════╝


# C#6, 75 bytes

string f(int r,int i=1)=>i*i>r?"":r%i==0?$"{i},{n(r,i+1)}{r/i},":n(r,i+1);  Based on the C# solution of downrep_nation, but recursive and golfed further down utilizing some new features from C#6. Basic algorithm is the same as the one presented by downrep_nation. The for-loop is turned to a recursion, thus the second parameter. recursion start is done by the default parameter, thus the function is called with the required single starting-number alone. • using expression based functions without a block avoids the return statement • string interpolation within ternary operator allows to join string concatenation and conditions As most answers here (yet) do not follow the exact output format from the examples, I keep it as it is, but as a drawback the function includes a single trailing comma at the result. • Nice first post! Commented May 3, 2016 at 21:05 # R, 36 31 bytes n=scan();c(d<-1:n^.5,n/d)^!n%%d  Try it online! -5 bytes thanks to Robin Ryder • 32 bytes with n^.5 instead of sqrt(n). Commented Jun 23, 2019 at 14:36 • You can go down to 31 bytes by duplicating the 1 many times. Commented Jun 23, 2019 at 14:42 # Matlab, 48 bytes n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]  • How does this work? Commented May 1, 2016 at 8:55 • Also, you devised an algorithm that I could not think of... How stupid I am. Commented May 1, 2016 at 8:55 • I find all the divisos up to sqrt(n) and then put each divisor d and n/d in my list. Commented May 1, 2016 at 9:08 • Added some rules. Maybe could save you some bytes. Commented May 1, 2016 at 9:09 • I haven't tested, but can't you use b=~mod(n,a) to save 1 byte? Commented May 1, 2016 at 10:52 # J, 26 bytes (],%)1+[:I.0=]|~1+i.@<.@%:  ## Explanation (],%)1+[:I.0=]|~1+i.@<.@%: Input: n %: Sqrt(n) <.@ Floor(Sqrt(n)) i.@ Get the range from 0 to Floor(Sqrt(n)), exclusive 1+ Add 1 to each ] Get n |~ Get the modulo of each in the range by n 0= Which values are equal to 0 (divisible by n), 1 if true else 0 [:I. Get the indices of ones 1+ Add one to each to get the divisors of n less than sqrt(n) % Divide n by each divisor ] Get the divisors , Concatenate them and return  # JavaScript (ES6) - 48 bytes f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x))  Not very efficient but works! Example below: let f=n=>[...Array(n+1).keys()].filter(x=>x&&!(n%x)); document.querySelector("input").addEventListener("change", function() { document.querySelector("output").value = f(Number(this.value)).join(", "); }); Divisors of <input type="number" min=0 step=1> are: <output></output> • Welcome to PPCG! Commented Nov 2, 2017 at 9:54 • This is $\mathcal{O}(n)$ and as such is not valid. Commented Jan 2, 2019 at 23:52 # MATL, 12 bytes tX^:\~ftGw/h  The approach is similar to that in @flawr's answer. Try it online! ### Explanation t % take input N. Duplicate. X^: % Generate range from 1 to sqrt(N) \ % modulo (remainder of division) ~f % indices of zero values: array of divisors up to sqrt(N) tGw/ % element-wise divide input by those divisors, to produce rest of divisors h % concatenate both arrays horizontally  • I do often wonder whether the combinded code of programs written in MATL would make a good RNG. Commented May 1, 2016 at 10:50 • @flawr That probably applies to pretty every code golf language :-) Commented May 1, 2016 at 10:51 # 05AB1E, 14 12 bytes Code: ÐtLDŠÖÏDŠ/ï«  Explanation: Ð # Triplicate input. tL # Push the list [1, ..., sqrt(input)]. D # Duplicate that list. Š # Pop a,b,c and push c,a,b. Ö # Check for each if a % b == 0. Ï # Only keep the truthy elements. D # Duplicate the list. Š # Pop a,b,c and push c,a,b /ï # Integer divide « # Concatenate to the initial array and implicitly print.  Uses CP-1252 encoding. Try it online!. ## Python 2, 64 bytes lambda n:sum([[x,n/x]for x in range(1,int(n**.5+1))if n%x<1],[])  This anonymous function outputs a list of divisors. The divisors are computed by trial division of integers in the range [1, ceil(sqrt(n))], which is O(sqrt(n)). If n % x == 0 (equivalent to n%x<1), then both x and n/x are divisors of n. Try it online # Jelly, 9 bytes ½Rḍ³Tµ³:;  As the other answers, this is O(√n) if we make the (false) assumption that integer division is O(1). ### How it works ½Rḍ³Tµ³:; Main link. Argument: n ½ Compute the square root of n. R Construct the range from 1 to the square root. ḍ³ Test each integer of that range for divisibility by n. T Get the indices of truthy elements. µ Begin a new, monadic chain. Argument: A (list of divisors) ³: Divide n by each divisor. ; Concatenate the quotients with A.  Try it online! • Commented May 2, 2016 at 5:35 # Javascript, 47 bytes d=(n,f=1,s='')=>n==f?s+n:d(n,f+1,n%f?s:s+f+',') # Mathematica, 50 bytes Similar to @flawr's solution. Performs trail division for x from 1 up to the square root of n and if divisible, saves it to a list as x and n / x. (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}&  • Note that ∣ requires 3 bytes to represent in UTF-8, making the 48 character string require 50 bytes in UTF-8 representation. ## Usage  f = (#2/#)~Join~#&@@{Cases[Range@Sqrt@#,x_/;x∣#],#}& f[1] {1, 1} f[2] {2, 1} f[6] {6, 3, 1, 2} f[9] {9, 3, 1, 3}  • Well, it requires 3 bytes... Commented May 1, 2016 at 9:29 • @KennyLau Yes, I was wrong, should have double-checked Commented May 1, 2016 at 9:36 ## JavaScript (ES6), 66 62 bytes f=(n,d=1)=>d*d>n?[]:d*d-n?n%d?f(n,d+1):[d,...f(n,d+1),n/d]:[d]  I thought I'd write a version that returned a sorted deduplicated list, and it actually turned out to be 4 bytes shorter... ## C#, 87 bytes Golfed String m(int v){var o="1";int i=1;while(++i<=v/2)if(v%i==0)o+=","+i;o+=","+v;return o;}  Ungolfed String m( Int32 v ) { String o = "1"; Int32 i = 1; while (++i <= v / 2) if (v % i == 0) o += "," + i; o += "," + v; return o; }  Full code using System; using System.Collections.Generic; namespace N { class P { static void Main( string[] args ) { List<Int32> li = new List<Int32>() { 1, 2, 6, 9, }; foreach (Int32 i in li) { Console.WriteLine( i + " »> " + m( i ) ); } Console.ReadLine(); } static String m( Int32 v ) { String o = "1"; Int32 i = 1; while (++i <= v / 2) if (v % i == 0) o += "," + i; o += "," + v; return o; } } }  Releases • v1.0 - 87 bytes - Initial solution. Notes • In the Golfed code, I use var's and int's instead of String's and Int32's to make the code shorter, while in the Ungolfed Code and Full Code I use String's and Int32's to make the code more readable. • I've heard that for is generally better than while. Commented May 1, 2016 at 10:53 • Your solution has a complexity of O(n) instead of O(sqrt(n))... Commented May 1, 2016 at 10:55 • @KennyLau it depends of the situation, in this case having a for loop would have the same length that the while loop has. In this case it is irrelevant having on or the having the other. Commented May 1, 2016 at 10:55 • But in this case it can save you a byte... Commented May 1, 2016 at 11:10 # Lua, 83 bytes s=''x=io.read()for i=1,x do if x%i==0 then s=s..i..', 'end end print(s:sub(1,#s-2))  I couldn't do better, unfortunately • 1. welcome to PPCG, hope you'll enjoy this site! 2. you can change ==0 to <1 to save some bytes. 3. you can use the ternary structure instead of if then end, but i don't know if it wil save any bytes. 4. your algorithm's complexity is O(n) which does not meet the requirement. Commented May 2, 2016 at 3:53 • All right. Does the list need to be ordered, or formatted appropriately? Commented May 2, 2016 at 5:10 • " The output list may contain duplicates. The output list does not need to be sorted. " Commented May 2, 2016 at 5:12 • Right lol. And do I need to print the result or an array containing it is enough? Commented May 2, 2016 at 12:51 • Well, either you print it or you return it (inside a function). Commented May 2, 2016 at 12:52 # Perl 6, 40 bytes {|(my@a=grep$_%%*,^.sqrt+1),|($_ X/@a)}  ### Explanation: { # this block has an implicit parameter named$_

# slip this list into outer list:
|(

my @a = grep
# Whatever lambda:
# checks if the block's parameter ($_) # is divisible by (%%) this lambda's parameter (*)$_ %% *,

# upto and exclude the sqrt of the argument
# then shift the Range up by one
^.sqrt+1
# (0 ..^ $_.sqrt) + 1 # would be clearer if written as: # 1 ..$_.sqrt+1
),
# slip this list into outer list
|(

# take the argument and divide it by each value in @a
$_ X/ @a # should use X[div] instead of X[/] so that it would return # Ints instead of Rats ) }  ### Usage: my &divisors = {|(my@a=grep$_%%*,^.sqrt+1),|(\$_ X/@a)}

.say for (1,2,6,9,10,50,99)».&divisors

(1 1)
(1 2 2 1)
(1 2 3 6 3 2)
(1 3 9 3)
(1 2 10 5)
(1 2 5 50 25 10)
(1 3 9 99 33 11)


## c#, 87 bytes

void f(int r){for(int i=1;i<=Math.Sqrt(r);i++){if(r%i==0)Console.WriteLine(i+" "+r/i);}


i do not know if this works for all numbers, i suspect it does.

but the complexity is right, so thats already something isnt it

# Ruby, 56 bytes

->n{a=[];(1..Math.sqrt(n)).map{|e|a<<e<<n/e if n%e<1};a}


# IA-32 machine code, 27 bytes

Hexdump:

60 33 db 8b f9 33 c0 92 43 50 f7 f3 85 d2 75 04
ab 93 ab 93 3b c3 5a 77 ec 61 c3


Source code (MS Visual Studio syntax):

    pushad;
xor ebx, ebx;
mov edi, ecx;
myloop:
xor eax, eax;
xchg eax, edx;
inc ebx;
push eax;
div ebx;
test edx, edx;
jnz skip_output;
stosd;
xchg eax, ebx;
stosd;
xchg eax, ebx;
skip_output:
cmp eax, ebx;
pop edx;
ja myloop;
ret;


First parameter (ecx) is a pointer to output, second parameter (edx) is the number. It doesn't mark the end of output in any way; one should prefill the output array with zeros to find the end of the list.

A full C++ program that uses this code:

#include <cstdint>
#include <vector>
#include <iostream>
#include <sstream>
__declspec(naked) void _fastcall doit(uint32_t* d, uint32_t n) {
_asm {
xor ebx, ebx;
mov edi, ecx;
myloop:
xor eax, eax;
xchg eax, edx;
inc ebx;
push eax;
div ebx;
test edx, edx;
jnz skip_output;
stosd;
xchg eax, ebx;
stosd;
xchg eax, ebx;
skip_output:
cmp eax, ebx;
pop edx;
ja myloop;
ret;
}
}
int main(int argc, char* argv[]) {
uint32_t n;
std::stringstream(argv[1]) >> n;
std::vector<uint32_t> list(2 * sqrt(n) + 3); // c++ initializes with zeros
doit(list.data(), n);
for (auto i = list.begin(); *i; ++i)
std::cout << *i << '\n';
}


The output has some glitches, even though it follows the spec (no need for sorting; no need for uniqueness).

Input: 69

Output:

69
1
23
3


The divisors are in pairs.

Input: 100

Output:

100
1
50
2
25
4
20
5
10
10


For perfect squares, the last divisor is output twice (it's a pair with itself).

Input: 30

Output:

30
1
15
2
10
3
6
5
5
6


If the input is close to a perfect square, the last pair is output twice. It's because of the order of checks in the loop: first, it checks for "remainder = 0" and outputs, and only then it checks for "quotient < divisor" to exit the loop.

# SmileBASIC, 49 bytes

INPUT N
FOR D=1TO N/D
IF N MOD D<1THEN?D,N/D
NEXT


Uses the fact that D>N/D = D>sqrt(N) for positive numbers

# C, 87 81 bytes

Improved by @ceilingcat, 81 bytes:

i,j;main(n,b)int**b;{for(;j=sqrt(n=atoi(b[1]))/++i;n%i||printf("%u,%u,",i,n/i));}


Try it online!

i;main(int n,char**b){n=atoi(b[1]);for(;(int)sqrt(n)/++i;n%i?:printf("%u,%u,",i,n/i));}


Compile with gcc div.c -o div -lm, and run with ./div <n>.

Bonus: An even shorter variant with O(n) time complexity and hardcoded n (46 bytes + length of n):

i,n=/*INSERT VALUE HERE*/;main(){for(;n/++i;n%i?:printf("%u,",i));}


Edit: Thank you to @Sriotchilism O'Zaic for pointing out that inputs should not be hardcoded, I modified the main submission to take the input via argv.

• Is n the input? Putting the input in a variable is not an accepted way of doing input here for a number of reasons. You can see more about our accepted and non-accepted input and output forms here: codegolf.meta.stackexchange.com/questions/2447/…. And if you are curious about a specific language (e.g. C) you can look here: codegolf.meta.stackexchange.com/questions/11924/…. Commented Jun 23, 2019 at 14:30
• @SriotchilismO'Zaic Yes, n is the input. I'll try modifying it so it takes the input some other way. Thank you for the info!
– user87616
Commented Jun 23, 2019 at 16:25

# APL(NARS), 22 chars, 44 bytes

{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}


test:

  f←{v∪⍵÷v←k/⍨0=⍵∣⍨k←⍳⌊√⍵}
f 1
1
f 2
1 2
f 6
1 2 6 3
f 9
1 3 9
f 90
1 2 3 5 6 9 90 45 30 18 15 10


# C# (Visual C# Interactive Compiler), 40 bytes

Just providing an updated C# answer

n=>Enumerable.Range(1,n).Where(x=>n%x<1)


Try it online!