# Closest to a square

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!
• Please notify me if this is a duplicate...
– Dion
May 14, 2020 at 16:04
• If the input integer is square may we output a single integer or must we repeat it? May 14, 2020 at 16:39
• @JonathanAllan it is up to you, although I would assume it's easier to repeat it.
– Dion
May 14, 2020 at 16:41
• This is OIES A033676 (lower number) and A033677 (higher number) May 16, 2020 at 22:19

# 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

– user92069
May 15, 2020 at 0:04
• 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. May 27, 2020 at 19:50
• @JubayerAbdullahJoy The OP mentioned that if the two numbers are the same, it is OK to output just one (see the comments). May 27, 2020 at 21:31
• oh, ok then. I must say your solution is very elegant :) May 27, 2020 at 22:26

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

# Python 2, 45 bytes

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


Try it online!

# 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]  # 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  • @Downvoter Any suggestion to improve my annswer? Jul 21, 2020 at 9:46 # 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! # 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! # 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. # Julia 54 bytes ## Try it n->begin i=findfirst(x->x^2>=n&&n%x==0,1:n);i,n÷i;end  # 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). # 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. # 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! # Java (JDK), 52 bytes n->{int i=n;for(;i*i>n|n%i>0;)i--;return n/i+","+i;}  Try it online! # dc, 39 bytes [d_3R/fq]sE?ddvd[_3R%0=E1-rd3RdlFx]dsFx  Try it online! 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.  # R, 484645 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. # Perl 5-pa, 37 bytes $_=0|sqrt;$_--while"@F"%$_;say"@F"/\$_


Try it online!

# Python 3, 7360 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!

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

• I think it needs to work for 1, right? Also s%a==0 -> s%a<1 May 14, 2020 at 17:23
• 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. May 15, 2020 at 8:46
• @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
– Dion
May 15, 2020 at 16:11

# SageMath, 63 60 bytes

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


Try it online!

# 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


# 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

• 13 bytes, different approach: Try it online! May 29, 2020 at 0:56

# 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

• Thank you, updated :) May 27, 2020 at 15:43
• Suggest b=n%i?b:n/(a=i) instead of n%i<1?a=i,b=n/i:0 Oct 14, 2020 at 15:51