10
\$\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\$
  • \$\begingroup\$ Please notify me if this is a duplicate... \$\endgroup\$ – Dion May 14 at 16:04
  • \$\begingroup\$ If the input integer is square may we output a single integer or must we repeat it? \$\endgroup\$ – Jonathan Allan May 14 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 at 16:41
  • \$\begingroup\$ This is OIES A033676 (lower number) and A033677 (higher number) \$\endgroup\$ – pizzapants184 May 16 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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I just got the idea when I scrolled past your answer. Clever answer though. \$\endgroup\$ – user92069 May 15 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\$ – Jubayer Abdullah Joy May 27 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\$ – dingledooper May 27 at 21:31
  • \$\begingroup\$ oh, ok then. I must say your solution is very elegant :) \$\endgroup\$ – Jubayer Abdullah Joy May 27 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\$.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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]
| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @Downvoter Any suggestion to improve my annswer? \$\endgroup\$ – Luis Mendo Jul 21 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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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).

| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.
| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pa, 37 bytes

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

Try it online!

| improve this answer | |
\$\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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I think it needs to work for 1, right? Also s%a==0 -> s%a<1 \$\endgroup\$ – Jonathan Allan May 14 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\$ – Olivier Grégoire May 15 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 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!

| improve this answer | |
\$\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
| improve this answer | |
\$\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

| improve this answer | |
\$\endgroup\$
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

| improve this answer | |
\$\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.