Closest to a square

Question

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 code-golf, so lowest byte count wins!

Answer 1

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

Answer 2

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

Answer 3

Python 2, 45 bytes

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

Try it online!

Answer 4

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]

Answer 5

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

Answer 6

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!

Answer 7

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!

Answer 8

Charcoal, 20 bytes

Ｎθ≔⊕⌈Φ₂θ¬﹪θ⊕ιηＩ⟦÷θηη

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:

Ｎθ

Input c.

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

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

Ｉ⟦÷θηη

Calculate and output a and b.

Answer 9

Julia 54 bytes

Try it

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

Answer 10

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

Answer 11

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.

Answer 12

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!

Answer 13

Java (JDK), 52 bytes

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

Try it online!

Answer 14

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.

Answer 15

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.

Answer 16

Perl 5 -pa, 37 bytes

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

Try it online!

Answer 17

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!

Answer 18

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!

Answer 19

SageMath, ⁶³ 60 bytes

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

Try it online!

Answer 20

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

Answer 21

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

Answer 22

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