11
\$\begingroup\$

The task

Given a positive integer c, output two integers a and b where a * b = c and each a and b is closest to sqrt(c) while still being integers.

Test cases

Input: 136
Output: 17 8
Input: 144
Output: 12 12
Input: 72
Output: 9 8
Input: 41
Output: 41 1
Input: 189
Output: 21 9

Rules

  1. a, b and c are all positive integers
  2. You may give a and b in any order, so for the first case an output of 8 17 is also correct
  3. This is , so lowest byte count wins!
\$\endgroup\$
4
  • \$\begingroup\$ Please notify me if this is a duplicate... \$\endgroup\$
    – Dion
    May 14 '20 at 16:04
  • \$\begingroup\$ If the input integer is square may we output a single integer or must we repeat it? \$\endgroup\$ May 14 '20 at 16:39
  • 2
    \$\begingroup\$ @JonathanAllan it is up to you, although I would assume it's easier to repeat it. \$\endgroup\$
    – Dion
    May 14 '20 at 16:41
  • \$\begingroup\$ This is OIES A033676 (lower number) and A033677 (higher number) \$\endgroup\$ May 16 '20 at 22:19

22 Answers 22

5
\$\begingroup\$

05AB1E, 3 bytes

Given an input \$ c \$, it outputs \$ a \$ and \$ b \$ as a list in increasing order. If \$ c \$ is a square, it outputs a single integer (which according to the OP is allowed).

ÑÅs

Try it online!

Explanation

Ñ     # All divisors
Ås    # Middle elements
\$\endgroup\$
4
  • \$\begingroup\$ I just got the idea when I scrolled past your answer. Clever answer though. \$\endgroup\$
    – user92069
    May 15 '20 at 0:04
  • \$\begingroup\$ The output should have two integers, but as you can see here, there is only one integer in case of input which is a power of 2. \$\endgroup\$ May 27 '20 at 19:50
  • \$\begingroup\$ @JubayerAbdullahJoy The OP mentioned that if the two numbers are the same, it is OK to output just one (see the comments). \$\endgroup\$ May 27 '20 at 21:31
  • \$\begingroup\$ oh, ok then. I must say your solution is very elegant :) \$\endgroup\$ May 27 '20 at 22:26
4
\$\begingroup\$

JavaScript (ES7), 35 bytes

f=(n,d=n**.5)=>n%d?f(n,-~d):[d,n/d]

Try it online!

How?

If \$n\$ is a square, \$d=\sqrt{n}\$ is an integer which obviously divides \$n\$, so we immediately have an answer. Otherwise, the first -~d will act as \$\lceil{d}\rceil\$ and the next ones as \$d+1\$. Either way, we stop as soon as \$n\equiv 0\pmod{d}\$ which in the worst case (i.e. if \$n\$ is prime) happens when \$d=n\$.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 45 bytes

i=n=input()
while(i*i>n)+n%i:i-=1
print n/i,i

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Jelly, 8 bytes

ÆDżṚ$SÞḢ

A monadic Link accepting a positive integer which yields a list of two positive integers.

Try it online!

How?

ÆDżṚ$SÞḢ - Link: positive integer, X   e.g. 12
ÆD       - divisors of X                    [1,2,3,4,6,12]
    $    - last two links as a monad:
   Ṛ     -   reverse                        [12,6,4,3,2,1]
  ż      -   zip                            [[1,12],[2,6],[3,4],[4,3],[6,2],[12,1]]
      Þ  - sort by:
     S   -   sum                            [[3,4],[4,3],[2,6],[6,2],[1,12],[12,1]]
       Ḣ - head                             [3,4]
\$\endgroup\$
2
\$\begingroup\$

MATL, 9 bytes

Z\J2/)Gy/

Try it online!

Explanation

Z\   % Implicit input. Array of divisors
J2/  % Push imaginary unit, divide by 2: gives 0.5j
)    % Index into the array. When used as an index, the imaginary unit means "end".
     % Thus the index 0.5j for [1 2 3 6] would give the 2nd entry (end=4th entry,
     % end/2 = 2nd entry, indexing is 1-based), whereas for [1 2 3 6 12] it would
     % give the "2.5-th" entry. This index is rounded up, so the result would be
     % the 3rd entry
G    % Push input again
y    % Duplicate second-top element in stack (that is, the selected entry)
/    % Divide
     % Implicitly display stack contents
\$\endgroup\$
1
  • \$\begingroup\$ @Downvoter Any suggestion to improve my annswer? \$\endgroup\$
    – Luis Mendo
    Jul 21 '20 at 9:46
2
\$\begingroup\$

C (gcc), 51 bytes

i;f(a,c)int*a;{for(i=0;i*i++<c;)c%i||(*a=i);c/=*a;}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 47 bytes

f=lambda n,v=1:[n/v,v]*(n/v-v<1>n%v)or f(n,v+1)

A recursive function.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 20 bytes

Nθ≔⊕⌈Φ₂θ¬﹪θ⊕ιηI⟦÷θηη

Try it online! Link is to verbose version of code. Technically only works up to a=2⁵³, but would be stupidly slow well before then anyway. Explanation:

Nθ

Input c.

≔⊕⌈Φ₂θ¬﹪θ⊕ιη

List all of the factors of c that do not exceed its floating-point square root, and take the largest b.

I⟦÷θηη

Calculate and output a and b.

\$\endgroup\$
2
\$\begingroup\$

Julia 54 bytes

Try it

n->begin i=findfirst(x->x^2>=n&&n%x==0,1:n);i,n÷i;end
\$\endgroup\$
1
\$\begingroup\$

Python 2, 52 48 bytes

f=lambda c,i=1:i*i>=c>c%i<1and(i,c/i)or f(c,i+1)

Try it online!

Simply increments i until it satisfies

i*i>=c and c%i==0

Then returns the pair (i, c/i).

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 34 bytes

.+
$*
(?<-2>(^(1)+?|\1))+$
$.1 $#1

Try it online! Link includes test cases. Explanation:

.+
$*

Convert c to unary.

(?<-2>(^(1)+?|\1))+$

The (1)+ matches a minimal substring a of 1s individually into the \2 stack, where they are popped off as the entire substring \1 is repeatedly matched b times until it reaches c. This popping mechanism thus prevents b from exceeding a, but as a is minimal it must therefore be the smallest factor not less than the square root. Excitingly, .NET allows you to populate the \2 stack on the first iteration of the (?<-2>) loop. (On the remainder of the loops, the ^ no longer matches, so the \1 alternative is used.)

$.1 $#1

Output a and b.

\$\endgroup\$
1
\$\begingroup\$

Erlang (escript), 68 bytes

f(X)->Y=lists:max([I||I<-lists:seq(1,X),X rem I==0,I*I=<X]),[Y,X/Y].

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 52 bytes

n->{int i=n;for(;i*i>n|n%i>0;)i--;return n/i+","+i;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

dc, 39 bytes

[d_3R/fq]sE?ddvd[_3R%0=E1-rd3RdlFx]dsFx

Try it online!

Or verify the test cases.


How it works:

Command  Stack (top on the right)

[        # Macro starts with stack at:
               # n d
               # Prints n/d and d, and then quits.
 d       # n d d
 _3R     # d n d
 /       # d n/d
 f       # Prints stack.
 q       # Quit this macro and the macro which called it.
]sE      # End macro and save it in register E.

?        # n  (Input values and push it on stack.)
dd       # n n n
v        # n n d
         #         d is a potential divisor of n;
         #         it's initialized to int(sqrt(n)).
d        # n n d d
[        # Start macro to be used as a loop.
 _3R     # n d n d
 %       # n d n%d
 0=E     # n d     If d divides n, call macro E to end.
 1-      # n d     New d = d - 1.
 r       # d n
 d       # d n n
 3R      # n n d
 d       # n n d d
         #         The stack is now set up correctly to
         #         go back to the top of the loop, with
         #         d now one step lower.
 lFx     # Call macro F to go back to the top of the loop.
]dsFx    # End macro, save it as F, and execute it.
\$\endgroup\$
1
\$\begingroup\$

R, 48 46 45 41 bytes

x=scan();b=1:x;a=b[!x%%b&b^2>=x][1];a;x/a

Try it online!

Finds first ([1]) divisor (which(!x%%b)) that is equal-to or greater than square-root (b^2>=x); returns this & reciprocal (a;x/a).
Previous approach (46 bytes) found divisor closest to centre of list-of-divisors, but couldn't be golfed-down so effectively.

\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pa, 37 bytes

$_=0|sqrt;$_--while"@F"%$_;say"@F"/$_

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 73 60 59 bytes

Not the shortest or best solution by any means, but I think it's a creative approach. Prints the two factors without separator between them and only (consistently) works for inputs up to 1008.

r=range(1000)
f=[a*b*(a*a>=a*b)for a in r for b in r].index

Try it online!

Python 3, 57 bytes

Still not the shortest solution, but it's at least somewhat expressive and clear what's going on.

lambda n:max((x,n/x)for x in range(1,n+1)if n%x<(x*x<=n))

Try it online!

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

Python 2, 66 bytes

def g(s):x=[[a,s/a]for a in range(1,s)if s%a==0];print x[len(x)/2]

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think it needs to work for 1, right? Also s%a==0 -> s%a<1 \$\endgroup\$ May 14 '20 at 17:23
  • \$\begingroup\$ It's usually accepted that a person providing the challenge does not answer their own challenge for a few days, letting other people trying to solve the challenge in the most available languages. \$\endgroup\$ May 15 '20 at 8:46
  • \$\begingroup\$ @OlivierGrégoire I fail to see how this stops people from posting their own answers. I've been outgolfed on this anyways even before I posted this \$\endgroup\$
    – Dion
    May 15 '20 at 16:11
0
\$\begingroup\$

SageMath, 63 60 bytes

def f(n):
 d=divisors(n)
 while len(d)>2:d=d[1:-1]
 return d

Try it online!

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

MathGolf, 7 bytes

─h½§_@/

Try it online!

Explanation

─          get a list of all divisors
 h½§       get the divisor at the middlemost index
           (if length is equal returns the smallest of the two middle elements)
    _      duplicate TOS
     @     rrot3 (pops input again and places it as the second item from the top)
      /    divides the input number by the extracted divisor, giving the other divisor
\$\endgroup\$
0
\$\begingroup\$

Pyth, 14 12 bytes

fsIJcQTs@Q2J

Try it online!

  • s@Q2 Starting from the floor of the square root of the input:

    • f find the first integer \$T\$ such that:

    • sIcQT \$T\$ divides the input

  • cQT gives the input divided by \$T\$ (ie. the other divisor) so we assign that value to J

  • The two divisors T and J are then implicitly printed

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

C++ (gcc), 108 bytes 103 bytes

#import<iostream>
int n,a,b,i;main(){for(std::cin>>n;i*i++<=n;)n%i<1?a=i,b=n/i:0;std::cout<<a<<' '<<b;}

Try it online!

Thanks to callingcat, for -5 bytes

\$\endgroup\$
2
  • \$\begingroup\$ Thank you, updated :) \$\endgroup\$ May 27 '20 at 15:43
  • \$\begingroup\$ Suggest b=n%i?b:n/(a=i) instead of n%i<1?a=i,b=n/i:0 \$\endgroup\$
    – ceilingcat
    Oct 14 '20 at 15:51

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.