# 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)). – flawr May 1 '16 at 8:40
• What is the difference between divisor and factor? – Leaky Nun May 1 '16 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. – flawr May 1 '16 at 8:44
• @flawr Updated accordingly. – Leaky Nun May 1 '16 at 8:45
• Should have more examples. 99 (1 3 9 11 33 99) – Brad Gilbert b2gills May 1 '16 at 18:53

# 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! – Rɪᴋᴇʀ May 3 '16 at 21:05 # Matlab, 48 bytes n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]  • How does this work? – Leaky Nun May 1 '16 at 8:55 • Also, you devised an algorithm that I could not think of... How stupid I am. – Leaky Nun May 1 '16 at 8:55 • I find all the divisos up to sqrt(n) and then put each divisor d and n/d in my list. – flawr May 1 '16 at 9:08 • Added some rules. Maybe could save you some bytes. – Leaky Nun May 1 '16 at 9:09 • I haven't tested, but can't you use b=~mod(n,a) to save 1 byte? – Luis Mendo May 1 '16 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! – Laikoni Nov 2 '17 at 9:54 • This is $\mathcal{O}(n)$ and as such is not valid. – ბიმო Jan 2 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. – flawr May 1 '16 at 10:50 • @flawr That probably applies to pretty every code golf language :-) – Luis Mendo May 1 '16 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!. • Care to provide an explanation? – Leaky Nun May 1 '16 at 10:42 • @KennyLau Added – Adnan May 1 '16 at 10: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 ║ ╚═════╩════════════════╝  # R, 36 bytes n=scan();d=1:sqrt(n);c(d,n/d)[!n%%d]  Try it online! # 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... – Leaky Nun May 1 '16 at 9:29 • @KennyLau Yes, I was wrong, should have double-checked – miles May 1 '16 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. – Leaky Nun May 1 '16 at 10:53 • Your solution has a complexity of O(n) instead of O(sqrt(n))... – Leaky Nun May 1 '16 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. – auhmaan May 1 '16 at 10:55 • But in this case it can save you a byte... – Leaky Nun May 1 '16 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. – Leaky Nun May 2 '16 at 3:53 • All right. Does the list need to be ordered, or formatted appropriately? – user6245072 May 2 '16 at 5:10 • " The output list may contain duplicates. The output list does not need to be sorted. " – Leaky Nun May 2 '16 at 5:12 • Right lol. And do I need to print the result or an array containing it is enough? – user6245072 May 2 '16 at 12:51 • Well, either you print it or you return it (inside a function). – Leaky Nun May 2 '16 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)


## 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!

• – Dennis May 2 '16 at 5:35

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