10
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You probably mean divisor, not factor. And I guess you want to have a time complexity of O(sqrt(n)). \$\endgroup\$ – flawr May 1 '16 at 8:40
  • \$\begingroup\$ What is the difference between divisor and factor? \$\endgroup\$ – Leaky Nun May 1 '16 at 8:42
  • \$\begingroup\$ 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. \$\endgroup\$ – flawr May 1 '16 at 8:44
  • \$\begingroup\$ @flawr Updated accordingly. \$\endgroup\$ – Leaky Nun May 1 '16 at 8:45
  • 1
    \$\begingroup\$ Should have more examples. 99 (1 3 9 11 33 99) \$\endgroup\$ – Brad Gilbert b2gills May 1 '16 at 18:53

19 Answers 19

3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice first post! \$\endgroup\$ – Rɪᴋᴇʀ May 3 '16 at 21:05
2
\$\begingroup\$

Matlab, 48 bytes

n=input('');a=1:n^.5;b=mod(n,a)<1;[a(b),n./a(b)]
\$\endgroup\$
  • \$\begingroup\$ How does this work? \$\endgroup\$ – Leaky Nun May 1 '16 at 8:55
  • \$\begingroup\$ Also, you devised an algorithm that I could not think of... How stupid I am. \$\endgroup\$ – Leaky Nun May 1 '16 at 8:55
  • \$\begingroup\$ I find all the divisos up to sqrt(n) and then put each divisor d and n/d in my list. \$\endgroup\$ – flawr May 1 '16 at 9:08
  • \$\begingroup\$ Added some rules. Maybe could save you some bytes. \$\endgroup\$ – Leaky Nun May 1 '16 at 9:09
  • 1
    \$\begingroup\$ I haven't tested, but can't you use b=~mod(n,a) to save 1 byte? \$\endgroup\$ – Luis Mendo May 1 '16 at 10:52
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Laikoni Nov 2 '17 at 9:54
  • \$\begingroup\$ This is \$\mathcal{O}(n)\$ and as such is not valid. \$\endgroup\$ – ბიმო Jan 2 at 23:52
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I do often wonder whether the combinded code of programs written in MATL would make a good RNG. \$\endgroup\$ – flawr May 1 '16 at 10:50
  • \$\begingroup\$ @flawr That probably applies to pretty every code golf language :-) \$\endgroup\$ – Luis Mendo May 1 '16 at 10:51
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Care to provide an explanation? \$\endgroup\$ – Leaky Nun May 1 '16 at 10:42
  • \$\begingroup\$ @KennyLau Added \$\endgroup\$ – Adnan May 1 '16 at 10:53
1
\$\begingroup\$

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 ║
╚═════╩════════════════╝
\$\endgroup\$
1
\$\begingroup\$

R, 36 bytes

n=scan();d=1:sqrt(n);c(d,n/d)[!n%%d]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ Well, it requires 3 bytes... \$\endgroup\$ – Leaky Nun May 1 '16 at 9:29
  • \$\begingroup\$ @KennyLau Yes, I was wrong, should have double-checked \$\endgroup\$ – miles May 1 '16 at 9:36
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I've heard that for is generally better than while. \$\endgroup\$ – Leaky Nun May 1 '16 at 10:53
  • \$\begingroup\$ Your solution has a complexity of O(n) instead of O(sqrt(n))... \$\endgroup\$ – Leaky Nun May 1 '16 at 10:55
  • \$\begingroup\$ @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. \$\endgroup\$ – auhmaan May 1 '16 at 10:55
  • \$\begingroup\$ But in this case it can save you a byte... \$\endgroup\$ – Leaky Nun May 1 '16 at 11:10
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Leaky Nun May 2 '16 at 3:53
  • \$\begingroup\$ All right. Does the list need to be ordered, or formatted appropriately? \$\endgroup\$ – user6245072 May 2 '16 at 5:10
  • \$\begingroup\$ " The output list may contain duplicates. The output list does not need to be sorted. " \$\endgroup\$ – Leaky Nun May 2 '16 at 5:12
  • \$\begingroup\$ Right lol. And do I need to print the result or an array containing it is enough? \$\endgroup\$ – user6245072 May 2 '16 at 12:51
  • \$\begingroup\$ Well, either you print it or you return it (inside a function). \$\endgroup\$ – Leaky Nun May 2 '16 at 12:52
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Ruby, 56 bytes

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

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;
    popad;
    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 {
        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;
        popad;
        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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.