# Simplify a square root

Given a positive integer n, simplify the square root √n into the form a√b by extracting all square factors. The outputted a,b should be positive integers with n = a^2 * b with b as small as possible.

You may output a and b in either order in any reasonable format. You may not omit outputs of 1 as implicit.

The outputs for n=1..36 as (a,b):

1 (1, 1)
2 (1, 2)
3 (1, 3)
4 (2, 1)
5 (1, 5)
6 (1, 6)
7 (1, 7)
8 (2, 2)
9 (3, 1)
10 (1, 10)
11 (1, 11)
12 (2, 3)
13 (1, 13)
14 (1, 14)
15 (1, 15)
16 (4, 1)
17 (1, 17)
18 (3, 2)
19 (1, 19)
20 (2, 5)
21 (1, 21)
22 (1, 22)
23 (1, 23)
24 (2, 6)
25 (5, 1)
26 (1, 26)
27 (3, 3)
28 (2, 7)
29 (1, 29)
30 (1, 30)
31 (1, 31)
32 (4, 2)
33 (1, 33)
34 (1, 34)
35 (1, 35)
36 (6, 1)


These are OEIS A000188 and A007913.

Related: A more complex version.

var QUESTION_ID=83814,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/83814/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

• We've had this before, and that was closed as a duplicate of the challenge linked here. Jun 26, 2016 at 19:39

# Jelly, 9 bytes

ÆE;0d2ZÆẸ


### How it works

ÆE;0d2ZÆẸ  Main link. Argument: n

ÆE         Exponents; generate the exponents of n's prime factorization.
;0       Append 0 since 1ÆE returns [].
d2     Divmod by 2.
Z    Zip/transpose to group quotients and remainders.
ÆẸ  Unexponent; turn the exponents of prime factorizations into integers.

• In UTF-8, it is, but Jelly uses a custom code page. The bytes link in the header points to it. Jun 27, 2016 at 5:51
• You post that comment a lot, so maybe you should make the bytes like clearer (for example: [bytes](link-to-byes) (not UTF-8). Nov 30, 2017 at 21:01

# Jelly, 6 bytes

²×¥þœi


Try It Online!

Outputs [b, a].

This does not use any prime factorization built-ins. Instead, it uses an array-oriented built-in œi (multi-dimensional index of), which is interestingly not found in any of APL/J/K/BQN.

### How it works

²×¥þœi    Monadic link. Input: the positive integer n.
²×¥þ      Compute the table of (x^2 * y) for both x and y in 1..n
For n = 3, this returns:
× | 1  4  9
--+--------
1 | 1  4  9
2 | 2  8 18
3 | 3 12 27
œi    Find the multi-dimensional index of n in the matrix above
[3, 1]


Since it finds the first occurrence in the matrix, b (first index) is guaranteed to be minimized, and n always appears at least once in the matrix at the coordinates [n, 1].

# Python 2, 43 bytes

k=n=input()
while n%k**2:k-=1
print k,n/k/k


Test it on Ideone.

## PARI/GP, 12 bytes

n->core(n,1)


core returns the squarefree part of n by default, but setting the second argument flag to 1 makes it return both parts. Output order is (b, a), e.g. (n->core(n,1))(12) -> [3, 2].

# MATL, 12 bytes

t:U\~f0)GyU/


Try it online!

### Explanation

t     % Take input n implicitly. Duplicate
:U    % Push [1 4 9 ... n^2]
\~    % True for entries that divide the input
f0)   % Get (1-based) index of the last (i.e. largest) dividing number
G     % Push input again
y     % Duplicate index of largest dividing number
U     % Square to recover largest dividing number
/     % Divide input by that. Implicitly display stack


# Julia, 32 bytes

\(n,k=n)=n%k^2>0?n\~-k:[k,n/k^2]


Try it online!

# Mathematica 34 bytes

#/.{a_ b_^_:>{a, b},_[b_,_]:>{1,b}}&


This says to replace all the input (#) according to the following rules: (1) a number, a, times the square root of b should be replaced by {a, b} and a function b to the power of whatever should be replaced by {1,b} . Note that the function assumes that the input will be of the form, Sqrt[n]. It will not work with other sorts of input.

This unnamed function is unusually cryptic for Mathematica. It can be clarified somewhat by showing its full form, followed by replacements of the original shorter forms.

Function[
ReplaceAll[
Slot[1],
List[
RuleDelayed[Times[Pattern[a,Blank[]],Power[Pattern[b,Blank[]],Blank[]]],List[a,b]],
RuleDelayed[Blank[][Pattern[b,Blank[]],Blank[]],List[1,b]]]]]


which is the same as

   ReplaceAll[
#,
List[
RuleDelayed[Times[Pattern[a,Blank[]],Power[Pattern[b,Blank[]],Blank[]]],List[a,b]],
RuleDelayed[Blank[][Pattern[b,Blank[]],Blank[]],List[1,b]]]]&


and

ReplaceAll[#,
List[RuleDelayed[
Times[Pattern[a, Blank[]],
Power[Pattern[b, Blank[]], Blank[]]], {a, b}],
RuleDelayed[Blank[][Pattern[b, Blank[]], Blank[]], {1, b}]]] &


and

ReplaceAll[#,
List[RuleDelayed[Times[a_, Power[b_, _]], {a, b}],
RuleDelayed[Blank[][b_, _], {1, b}]]] &


and

ReplaceAll[#, {RuleDelayed[a_*b^_, {a, b}], RuleDelayed[_[b_, _], {1, b}]}]&


and

ReplaceAll[#, {a_*b^_ :> {a, b}, _[b_, _] :> {1, b}}] &


## 05AB1E, 14 bytes

Lv¹ynÖi¹yn/y‚ï


Explained

Lv              # for each x in range(1,N) inclusive
¹ynÖi         # if N % x^2 == 0
¹yn/y‚ï  # create [N/x^2,x] pairs, N=12 -> [12,1] [3,2]
# implicitly output last found pair


Try it online

# Python, 74 Bytes

def e(k):a=filter(lambda x:k/x**2*x*x==k,range(k,0,-1))[0];return a,k/a**2


Straightforward enough.

# Pyth, 15 bytes

/Q^
ef!%Q^T2SQ2


Test suite.

## Matlab, 51 bytes

x=input('');y=1:x;z=y(~rem(x,y.^2));a=z(end)
x/a^2


Explanation

x=input('')       -- takes input
y=1:x             -- numbers from 1 to x
z=y(~rem(x,y.^2)) -- numbers such that their squares divide x
a=z(end)          -- biggest such number (first part of output)
x/a^2             -- remaining part


# JavaScript (ECMAScript 2016), 40 bytes

n=>{for(k=n;n%k**2;k--);return[k,n/k/k]}


Basically a JavaScript port of Dennis's Python 2 answer.

Note: it doesn't work in strict mode, because k is not initialized anywhere. To make it work in strict mode, k=n in the loop should be changed to let k=n.

# Haskell, 43> 42 bytes

Brute force solution.

Saved 1 byte thanks to Xnor

f n=[(x,y)|y<-[1..],x<-[1..n],x*x*y==n]!!0

• Nice solution, I like how it doesn't use mod or div. I think you can do y<-[1..] due to laziness.
– xnor
Jun 27, 2016 at 11:02
• Yes, you are right. It wasn't possible with my first solution last[(x,y)|x<-[1..n],y<-[1..n],x*x*y==n] but now it will work. Thanks. Do you have your own solution in Haskell? Jun 27, 2016 at 12:06

## APL, 25 chars

 {(⊢,⍵÷×⍨)1+⍵-0⍳⍨⌽⍵|⍨×⍨⍳⍵}


In English:

• 0⍳⍨⌽⍵|⍨×⍨⍳⍵: index of the largest of the squares up to n that divides completely n;
• 1+⍵-: the index is in the reversed array, so adjust the index
• (⊢,⍵÷×⍨): produce the result: the index itself (a) and the quotient b (that is, n÷a*a)

Test:

     ↑{(⊢,⍵÷×⍨)⊃z/⍨0=⍵|⍨×⍨z←⌽⍳⍵}¨⍳36
1  1
1  2
1  3
2  1
1  5
1  6
1  7
2  2
3  1
1 10
1 11
2  3
1 13
1 14
1 15
4  1
1 17
3  2
1 19
2  5
1 21
1 22
1 23
2  6
5  1
1 26
3  3
2  7
1 29
1 30
1 31
4  2
1 33
1 34
1 35
6  1


# JavaScript (ECMAScript 6), 35 bytes

f=(n,k=n)=>n/k%k?f(n,--k):[k,n/k/k]


# JavaScript 1+, 37 B

for(k=n=prompt();n/k%k;--k);[k,n/k/k]


# J, 19 bytes

(0|:0 2#:])&.(_&q:)


Try it online!

Same as the Jelly solution.

# Vyxal, 9 bytes

K'∆²;t₍/√


Try it Online!

Very cool and good. Outputs as [constant, surd]

## Explained

K'∆²;t₍√/
K        # from the factors of the input,
'∆²;    # keep only square numbers
t   # and keep the last.
₍√/ # Push [sqrt(^), input / ^]


Python 2.7 (ungolfed) - 181 Bytes

def e(n):
for x in range(1,n+1):
r=(1,x)
for i in range(1,x+1):
l=i**.5
for j in range(1,x+1):
if i*j==x and l%1==0 and j<r[1]:r=(int(l),j)
print x,r


Run as: e(number) eg. e(24)

Sample output:

>> e(24)
1 (1, 1)
2 (1, 2)
3 (1, 3)
4 (2, 1)
5 (1, 5)
6 (1, 6)
7 (1, 7)
8 (2, 2)
9 (3, 1)
10 (1, 10)
11 (1, 11)
12 (2, 3)
13 (1, 13)
14 (1, 14)
15 (1, 15)
16 (4, 1)
17 (1, 17)
18 (3, 2)
19 (1, 19)
20 (2, 5)
21 (1, 21)
22 (1, 22)
23 (1, 23)
24 (2, 6)

• Please attempt to golf your answer as much as possible, this is a code-golf Nov 30, 2017 at 18:50