16
\$\begingroup\$

Given a natural number n write a program or function to get a list of all the possible two factors multiplications that can be used to achieve n. To understand better what is pretended you can go to http://factornumber.com/?page=16777216 to see when n is 16777216 we get the following list:

 2 ×ばつ 8388608 
 4 ×ばつ 4194304 
 8 ×ばつ 2097152 
 16 ×ばつ 1048576 
 32 ×ばつ 524288 
 64 ×ばつ 262144 
 128 ×ばつ 131072 
 256 ×ばつ 65536 
 512 ×ばつ 32768 
1024 ×ばつ 16384
2048 ×ばつ 8192
4096 ×ばつ 4096

No need to pretty print things like here. The requirement is that each entry (pair of factors) is well distinguished from each other and inside each pair, the first factor is also well distinguished from the other. If you choose to return a list/array, the inside element can be a list/array with two elements, or some structure of your language that supports a pair of things like C++ std::pair.

Do not print the multiplication by 1 entry, nor repeat entries with the first factor commuted by the second, as they are pretty useless.

No winner; it will be a per language basis code golf.

Luis Mendo
107k10 gold badges139 silver badges382 bronze badges
asked Dec 2, 2017 at 22:18
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Could you possibly add a smaller test case, such as 30? \$\endgroup\$ Commented Dec 2, 2017 at 22:27
  • 1
    \$\begingroup\$ @cairdcoinheringaahing You can use factornumber.com to generate more test cases. \$\endgroup\$ Commented Dec 2, 2017 at 22:39
  • 1
    \$\begingroup\$ I've seen this "per language" competition recently. What's the point? Most Qs don't get more than 1 or 2 As per language, and you still can select just one A as correct. \$\endgroup\$ Commented Dec 2, 2017 at 23:54
  • 8
    \$\begingroup\$ @fedes. It's usually because there's no point in comparing between languages (i.e. Java vs. Jelly). \$\endgroup\$ Commented Dec 3, 2017 at 0:06
  • 2
    \$\begingroup\$ Related codegolf.stackexchange.com/q/141004/73398 \$\endgroup\$ Commented Dec 3, 2017 at 14:37

33 Answers 33

1
2
6
\$\begingroup\$

Java (OpenJDK 8), (削除) 81 (削除ここまで) (削除) 66 (削除ここまで) 65 bytes

  • -15 Bytes thanks to Olivier Grégoire.
  • -1 Byte: ++j<=i/j -> j++<i/j.
i->{for(int j=1;j++<i/j;)if(i%j<1)System.out.println(j+" "+i/j);}

Try it online!

Old one (for reference)

Java (OpenJDK 8), 126 bytes

i->{java.util.stream.IntStream.range(2,i).filter(d->d<=i/d&&i%d==0).forEach(e->System.out.println(""+e+"x"+i/e));return null;}

Try it online!

First codegolf submit and first lambda usage. Future self, please forgive me for the code.

answered Dec 4, 2017 at 13:09
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Nice first entry! Welcome to PPCG! Here is it golfed down to 66 bytes by removing all the superfluous: I couldn't golf your algorithm though. \$\endgroup\$ Commented Dec 4, 2017 at 14:03
5
\$\begingroup\$

05AB1E, 8 bytes

Ñ‚ø2äн¦

Try it online!

answered Dec 2, 2017 at 23:17
\$\endgroup\$
2
  • 2
    \$\begingroup\$ +1 from me we have nearly the same solutions. I thought of this 8-byter \$\endgroup\$ Commented Dec 2, 2017 at 23:21
  • \$\begingroup\$ @Mr.Xcoder: Ah yes, nice :) It's too bad that the map is required there. \$\endgroup\$ Commented Dec 3, 2017 at 8:41
5
\$\begingroup\$

C (gcc), (削除) 58 (削除ここまで) (削除) 54 (削除ここまで) 53 bytes

f(N,j){for(j=1;j++*j<N;)N%j||printf("|%d,%d",j,N/j);}

Try it online!

answered Dec 2, 2017 at 23:05
\$\endgroup\$
1
  • \$\begingroup\$ Nice. This would appear better in the "%dx%d " format. \$\endgroup\$ Commented Mar 12 at 19:04
5
\$\begingroup\$

Python 2, 51 bytes

f=lambda n,k=2:n/k/k*[f]and[(k,n/k)][n%k:]+f(n,k+1)

Try it online!

51 bytes (thanks to Luis Mendo for a byte)

lambda n:[(n/k,k)for k in range(1,n)if(k*k<=n)>n%k]

Try it online!

51 bytes

lambda n:[(n/k,k)for k in range(1,n)if n/k/k>n%k*n]

Try it online!

answered Dec 2, 2017 at 22:46
\$\endgroup\$
3
  • \$\begingroup\$ I like the use of [f]. \$\endgroup\$ Commented Dec 2, 2017 at 22:52
  • 1
    \$\begingroup\$ You can save 1 byte in the second version with lambda n:[(n/k,k)for k in range(1,n)if(k*k<=n)>n%k] \$\endgroup\$ Commented Dec 3, 2017 at 2:49
  • \$\begingroup\$ MemoryError on all approaches for 1512518520 \$\endgroup\$ Commented Dec 5, 2017 at 0:37
4
\$\begingroup\$

Haskell, 38 bytes

f x=[(a,b)|a<-[2..x],b<-[2..a],a*b==x]

Try it online!

answered Dec 2, 2017 at 23:10
\$\endgroup\$
1
  • \$\begingroup\$ Time out for 1512518520 \$\endgroup\$ Commented Dec 5, 2017 at 0:40
3
\$\begingroup\$

APL (Dyalog), 28 bytes

{(⊢,⍵÷⊢) ̈o/⍨0=⍵|⍨o←1↓⍳⌊⍵*.5}

Try it online!

answered Dec 2, 2017 at 22:41
\$\endgroup\$
3
\$\begingroup\$

Perl 6, 38 bytes

{map {$^a,$_/$a},grep $_%%*,2.. .sqrt}

Try it

Expanded:

{ # bare block lambda with implicit parameter 「$_」
 map
 { $^a, $_ / $a }, # map the number with the other factor
 grep
 $_ %% *, # is the input divisible by *
 2 .. .sqrt # from 2 to the square root of the input
}
answered Dec 3, 2017 at 1:50
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 8 bytes

×ばつ≜Ċo}u

Try it online!

Explanation

×ばつ≜Ċo}u
{ }u List the unique outputs of this predicate.
 ×ばつ Pick a list of integers whose product is the input.
 ≜ Force concrete values for its elements.
 Ċ Force its length to be 2.
 o Sort it and output the result.

The ×ばつ part does not include 1s in its output, so for input N it gives [N] instead of [1,N], which is later culled by Ċ. I'm not entirely sure why ≜ is needed...

answered Dec 3, 2017 at 10:24
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The ≜ is needed because otherwise there are no choice points for u: a length-2 list whose product is the input is the only answer if you don't actually ask for the values of the list. \$\endgroup\$ Commented Dec 4, 2017 at 7:01
2
\$\begingroup\$

Japt, 9 bytes

â¬Å£[XZo]

Test it online! Returns an array of arrays, with some nulls at the end; -R flag added to show output more clearly.

answered Dec 2, 2017 at 22:28
\$\endgroup\$
3
  • 1
    \$\begingroup\$ So I think the ` -R` should be considered for the byte count... \$\endgroup\$ Commented Dec 2, 2017 at 23:41
  • 3
    \$\begingroup\$ @sergiol, no, in this case it's just for formatting the output for better readability. \$\endgroup\$ Commented Dec 3, 2017 at 11:07
  • \$\begingroup\$ Exactly the solution I had, except I filtered the nulls out at the end. \$\endgroup\$ Commented Dec 3, 2017 at 11:08
2
\$\begingroup\$

Jelly, 8 bytes 

1⁄2ḊpP=\Ðf

A monadic link taking a number and returning a list of lists (pairs) of numbers.

Try it online! (times out on TIO for the 16777216 example since it would create a list of 68.7 billion pairs and filter down to those with the correct product!)

How?

1⁄2ḊpP=\Ðf - Link: number, n e.g. 144
1⁄2 - square root of n 12
 Ḋ - dequeue* [2,3,4,5,6,7,8,9,10,11,12]
 p - Cartesian product** [[2,1],[2,2],...[2,144],[3,1],...,[3,144],...,[12,144]
 Ðf - filter keep if:
 \ - last two links as a dyad (n is on the right):
 P - product
 = - equals
 - [[2,72],[3,48],[4,36],[6,24],[8,18],[9,16],[12,12]]

* Ḋ, dequeue, implicitly makes a range of a numeric input prior to acting, and the range function implicitly floors its input, so with, say, n=24 the result of 1⁄2 is 4.898...; the range becomes [1,2,3,4]; and the dequeued result is [2,3,4]

** Similarly to above, p, Cartesian product, makes ranges for numeric input - here the right argument is n hence the right argument becomes [1,2,3,...,n] prior to the actual Cartisian product taking place.

answered Dec 3, 2017 at 0:58
\$\endgroup\$
2
\$\begingroup\$

Husk, 8 bytes

tüOSze↔Ḋ

Try it online!

Explanation

tüOSze↔Ḋ Implicit input, say n=30.
 Ḋ List of divisors: [1,2,3,5,6,10,15,30]
 ↔ Reverse: [30,15,10,6,5,3,2,1]
 Sze Zip with original: [[1,30],[2,15],[3,10],[5,6],[6,5],[10,3],[15,2],[30,1]]
 üO Deduplicate by sort: [[1,30],[2,15],[3,10],[5,6]]
t Drop first pair: [[2,15],[3,10],[5,6]]
answered Dec 3, 2017 at 9:18
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 55 bytes

n=>eval('for(k=1,a=[];k*++k<n;n%k||a.push([k,n/k]));a')

Demo

let f =
n=>eval('for(k=1,a=[];k*++k<n;n%k||a.push([k,n/k]));a')
console.log(JSON.stringify(f(6)))
console.log(JSON.stringify(f(7)))
console.log(JSON.stringify(f(16777216)))

Try It Online!

Stan Strum
4473 silver badges14 bronze badges
answered Dec 2, 2017 at 22:42
\$\endgroup\$
4
  • \$\begingroup\$ Is it me or does this fail for 6? \$\endgroup\$ Commented Dec 4, 2017 at 10:33
  • \$\begingroup\$ @Neil "We can fix it." (Thanks for reporting!) \$\endgroup\$ Commented Dec 4, 2017 at 10:41
  • \$\begingroup\$ How can I supply a number to test? \$\endgroup\$ Commented Dec 5, 2017 at 21:41
  • \$\begingroup\$ You can Try it online! \$\endgroup\$ Commented Dec 5, 2017 at 21:47
2
\$\begingroup\$

Jelly, (削除) 12 (削除ここまで) 7 bytes

ḊŒċP=\Ƈ

Try it online!

answered Dec 2, 2017 at 22:26
\$\endgroup\$
0
1
\$\begingroup\$

Python 2, 59 bytes

lambda N:{(n,N/n,n)[n>N/n:][:2]for n in range(2,N)if N%n<1}

Try it online!

answered Dec 2, 2017 at 22:31
\$\endgroup\$
2
  • \$\begingroup\$ tio.run/##FcnRCoMgFAbgVzk3AwVh84AQsu0RfIHqwig3YfsNk2BEz27r7oNv/… — Memory error? \$\endgroup\$ Commented Dec 5, 2017 at 0:30
  • \$\begingroup\$ @sergiol Yes, a MemoryError, since Python tries to evaluate range(2,N) and store it as a list, yet the allocated memory does not suffice. One could try replace range with xrange (Python 2's range generator), though this exceeds TIO's one minute of maximum runtime. On a machine with enough memory and time, this program should terminate and return the correct answer. \$\endgroup\$ Commented Dec 5, 2017 at 16:01
1
\$\begingroup\$

Jelly, 9 bytes

ÆḌḊμżUṢ€Q

Try it online!

answered Dec 2, 2017 at 23:01
\$\endgroup\$
1
\$\begingroup\$

Octave, 42 bytes

@(n)[y=find(~mod(n,x=2:n)&x.^2<=n)+1;n./y]

Try it online!

answered Dec 3, 2017 at 3:06
\$\endgroup\$
1
\$\begingroup\$

PHP, 70 bytes

As string (70 bytes):

$i++;while($i++<sqrt($a=$argv[1])){echo !($a%$i)?" {$i}x".($a/$i):'';}

As array dump (71 bytes):

$i++;while($i++<sqrt($a=$argv[1]))!($a%$i)?$b[$i]=$a/$i:'';print_r($b);

(im not sure if i can use return $b; instead of print_r since it no longer outputs the array, otherwise i can save 2 bytes here. )

The array gives the results like:

Array
(
 [2] => 8388608
 [4] => 4194304
 [8] => 2097152
 [16] => 1048576
answered Dec 3, 2017 at 13:55
\$\endgroup\$
2
  • \$\begingroup\$ "If you choose to return a list/array" To me it means you can print or return as you see fit. \$\endgroup\$ Commented Dec 4, 2017 at 6:17
  • \$\begingroup\$ On second thought, returning should be valid for a function, and printing for a program. You seem to have a snippet/program, not a function, so I'd say in this case you should be printing. \$\endgroup\$ Commented Dec 4, 2017 at 6:20
1
\$\begingroup\$

Wolfram Language (Mathematica), 41 bytes

nRest@Union[Sort@{#,n/#}&/@Divisors@n]

Try it online!

is the Function operator, which introduces an unnamed function with named parameter n.

answered Dec 3, 2017 at 15:47
\$\endgroup\$
1
\$\begingroup\$

Factor, 58

Well, there has to be some Factor in this question!

[ divisors dup reverse zip dup length 1 + 2 /i head rest ]

It's a quotation. call it with the number on the stack, leaves an assoc (an array of pairs) on the stack.

I'm never sure if all the imports count or not, as they're part of the language. This one uses:

USING: math.prime.factors sequences assocs math ;

(If they count, I should look for a longer solution with shorter imports, which is kind of silly)

As a word:

: 2-factors ( x -- a ) divisors dup reverse zip dup length 1 + 2 /i head rest ;
50 2-factors .
 --> { { 2 25 } { 5 10 } }
answered Dec 4, 2017 at 5:59
\$\endgroup\$
0
1
\$\begingroup\$

Ruby, 43 bytes

->n{(2..n**0.5).map{|x|[[x,n/x]][n%x]}-[p]}

Try it online!

How it works:

For every number up to sqrt(n), generate the pair [[x, n/x]], then take the n%xth element of this array. If n%x==0 this is [x, n/x], otherwise it's nil. when done, remove all nil from the list.

answered Dec 4, 2017 at 14:27
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, (削除) 49 (削除ここまで) (削除) 34 (削除ここまで) 38 bytes

n->[[d,n/d]|d<-divisors(n),d>1&d<=n/d]

Try it online!

Set builder notation for all pairs [d, n/d] where d runs through all divisors d of n subject to d > 1 and d <= n/d.

Huge improvement by alephalpha.

answered Dec 5, 2017 at 8:32
\$\endgroup\$
2
  • 1
    \$\begingroup\$ n->[[d,n/d]|d<-divisors(n),d<=n/d] \$\endgroup\$ Commented Dec 28, 2017 at 0:36
  • \$\begingroup\$ @alephalpha Good one. But had to change it a bit because it output also the factorization with 1. \$\endgroup\$ Commented Dec 28, 2017 at 10:13
1
\$\begingroup\$

Perl 5, 53 + 2 (-p flag) = 55 bytes

$_="@{[map{$_,$n/$_.$/}grep!($n%$_),2..sqrt($n=$_)]}"

Ungolfed:

while (defined $_ = <>) {
 $n = $_;
 $_ = qq(@{[
 map{ ($_, ($n / $_) . "\n") } grep { !($n % $_) } (2 .. sqrt($n))
 ]});
 print($_);
}

Try it online.

answered Dec 28, 2017 at 11:31
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 7 bytes

K~/Z's=

Try it Online!

(not anymore) messy.

answered Aug 27, 2021 at 23:21
\$\endgroup\$
2
  • \$\begingroup\$ 7 bytes \$\endgroup\$ Commented Aug 30, 2021 at 20:18
  • \$\begingroup\$ @AaronMiller Nice use of ~ :) \$\endgroup\$ Commented Aug 30, 2021 at 20:19
0
\$\begingroup\$

Husk, (削除) 14 (削除ここまで) 12 bytes

tumoOSe`/0Ḋ0

Try it online!

Explanation

tum(OSe`/0)Ḋ0 -- input 0, eg. 30
 Ḋ0 -- divisors [1..0]: [1,2,3,5,6,10,15,30]
 m( ) -- map the following function (example on 10):
 Se -- create list with 10 and ..
 `/0 -- .. flipped division by 0 (30/10): [10,3]
 O -- sort: [3,10]
 -- [[1,30],[2,15],[3,10],[5,6],[5,6],[3,10],[2,15],[1,30]]
 u -- remove duplicates: [[1,30],[2,15],[3,10],[5,6]]
t -- tail: [[2,15],[3,10],[5,6]]
answered Dec 3, 2017 at 0:56
\$\endgroup\$
0
\$\begingroup\$

APL+WIN, 32 bytes

m,[.1]n÷m←(0=m|n)/m←1↓⍳⌊(n←⎕)*.5

Explanation:

(n←⎕) Prompts for screen input
m←(0=m|n)/m←1↓⍳⌊(n←⎕)*.5 Calculates the factors dropping the first
m,[.1]n÷ Identifies the pairs and concatenates into a list.
answered Dec 3, 2017 at 10:16
\$\endgroup\$
0
\$\begingroup\$

Add++, (削除) 18 (削除ここまで) 15 bytes

L,F@pB]dBRBcE#S

Try it online!

How it works

L, - Create a lambda function
 - Example argument: 30
 F - Factors; STACK = [1 2 3 5 6 10 15]
 @ - Reverse; STACK = [15 10 6 5 3 2 1]
 p - Pop; STACK = [15 10 6 5 3 2]
 B] - Wrap; STACK = [[15 10 6 5 3 2]]
 d - Duplicate; STACK = [[15 10 6 5 3 2] [15 10 6 5 3 2]]
 BR - Reverse; STACK = [[15 10 6 5 3 2] [2 3 5 6 10 15]]
 Bc - Zip; STACK = [[15 2] [10 3] [6 5] [5 6] [3 10] [2 15]]
 E# - Sort each; STACK = [[2 15] [3 10] [5 6] [5 6] [3 10] [2 15]]
 S - Deduplicate; STACK = [[[2 15] [3 10] [5 6]]]
answered Dec 3, 2017 at 11:13
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 53 bytes

Array[s[[{#,-#}]]&,⌈Length[s=Divisors@#]/2⌉-1,2]&

Try it online!

answered Dec 3, 2017 at 14:58
\$\endgroup\$
0
\$\begingroup\$

Befunge-93, 56 bytes

&1vg00,+55./.: <
+1< v`\g00/g00:p00
_ ^@_::00g%!00g\#v

Try It Online

answered Dec 3, 2017 at 12:30
\$\endgroup\$
0
0
\$\begingroup\$

Julia 0.6, 41 bytes

~x=[(y,div(x,y))for y=2:x if x%y<1>y^2-x]

Try it online!

Redefines the inbuild unary operator ~ and uses an array comprehension to build the output.

  • div(x,y) is neccessary for integer division. x/y saves 5 bytes but the output is ~4=(2,2.0).
  • Julia allows chaining the comparisons, saving one byte.
  • Looping all the way to x avoids Int(floor(√x)).
answered Dec 22, 2017 at 23:00
\$\endgroup\$
0
\$\begingroup\$

APL NARS 99 chars

r←f w;i;h
r←⍬⋄i×ばつ⍳w≠+w
A:i×ばつ⍳∼0=i×ばつ⍳i>h←w÷i⋄r←r,⊂i h⋄→A

9+46+41+3=99 Test: (where not print nothing, it return something it return ⍬ the list null one has to consider as "no solution")

 f 101 
 f 1 2 3
 f '1'
 f '123'
 f 33 1.23
 f 1.23
 ⎕←⊃f 16777216 
 2 8388608
 4 4194304
 8 2097152
 16 1048576
 32 524288
 64 262144
 128 131072
 256 65536
 512 32768
1024 16384
2048 8192
4096 4096
 f 123
3 41
answered Dec 23, 2017 at 12:55
\$\endgroup\$
1
2

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.