# 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)). May 1, 2016 at 8:40
• What is the difference between divisor and factor? 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. May 1, 2016 at 8:44
• @flawr Updated accordingly. May 1, 2016 at 8:45
• Should have more examples. 99 (1 3 9 11 33 99) 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! 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). Jun 23, 2019 at 14:36 • You can go down to 31 bytes by duplicating the 1 many times. 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? May 1, 2016 at 8:55 • Also, you devised an algorithm that I could not think of... How stupid I am. 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. May 1, 2016 at 9:08 • Added some rules. Maybe could save you some bytes. May 1, 2016 at 9:09 • I haven't tested, but can't you use b=~mod(n,a) to save 1 byte? 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! Nov 2, 2017 at 9:54 • This is $\mathcal{O}(n)$ and as such is not valid. 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. May 1, 2016 at 10:50 • @flawr That probably applies to pretty every code golf language :-) 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! • 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... May 1, 2016 at 9:29 • @KennyLau Yes, I was wrong, should have double-checked 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. May 1, 2016 at 10:53 • Your solution has a complexity of O(n) instead of O(sqrt(n))... 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. May 1, 2016 at 10:55 • But in this case it can save you a byte... 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. May 2, 2016 at 3:53 • All right. Does the list need to be ordered, or formatted appropriately? May 2, 2016 at 5:10 • " The output list may contain duplicates. The output list does not need to be sorted. " May 2, 2016 at 5:12 • Right lol. And do I need to print the result or an array containing it is enough? May 2, 2016 at 12:51 • Well, either you print it or you return it (inside a function). 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/…. 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! 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!