Упростить квадратный корень

29

Учитывая положительное целое число n, упростите квадратный корень √nв форму a√b, извлекая все квадратные факторы. Выходные данные a,bдолжны быть положительными целыми числами n = a^2 * bс bкак можно меньшим.

Вы можете выводить aи bв любом порядке в любом разумном формате. Вы не можете опускать выходные данные 1как неявные.

Выходы n=1..36как (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)

Это OEIS A000188 и A007913 .

Связанный: более сложная версия .

Показать фрагмент кода

code-golf math arithmetic XNOR
источник
У нас было это раньше , и это было закрыто как дубликат вызова, связанного здесь.
flawr

Ответы:

13

Желе , 9 байт

ÆE;0d2ZÆẸ

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это работает

Æ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.
Деннис
источник
3
В UTF-8 это так, но Jelly использует пользовательскую кодовую страницу. В байтах ссылаются в точках заголовка к нему.
Деннис
Вы отправляете , что комментарий много, так что, может быть , вы должны сделать байты как понятнее (например: [bytes](link-to-byes) (not UTF-8).
NoOneIsHere
12

PARI / GP, 12 байт

n->core(n,1)

corenпо умолчанию возвращает часть без квадратов , но установив флаг второго аргумента в 1, он возвращает обе части. Выходной заказ (b, a), например (n->core(n,1))(12) -> [3, 2].

Sp3000
источник
11

Python 2, 43 байта

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

Проверьте это на Ideone .

Деннис
источник
6

MATL , 12 байт

t:U\~f0)GyU/

Попробуйте онлайн!

объяснение

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
Луис Мендо
источник
2

Mathematica 34 байта

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

Это говорит о замене всех input ( #) в соответствии со следующими правилами: (1) число, a , умноженное на квадратный корень из b , {a, b} и функция b в степень того, что должно быть заменено на {1, b } Обратите внимание, что функция предполагает, что вход будет иметь форму,Sqrt[n] . Это не будет работать с другими видами ввода.

Эта безымянная функция необычайно загадочна для Mathematica. Это можно уточнить, показав его полную форму с последующими заменами оригинальных более коротких форм.

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]]]]]

который так же, как

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

а также

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

а также

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

а также

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

а также

ReplaceAll[#, {a_*b^_ :> {a, b}, _[b_, _] :> {1, b}}] &
DavidC
источник
1

Matlab, 51 байт

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

объяснение

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
pajonk
источник
1

JavaScript (ECMAScript 2016), 40 байт

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

В основном порт JavaScript Дениса Python 2 ответа .

Попробуйте это на JSBin .

Примечание: он не работает в строгом режиме, потому что kнигде не инициализируется. Чтобы это работало в строгом режиме, k=nв цикле должно быть изменено значение let k=n.

Михал Перлаковский
источник
1

Haskell, 43> 42 байта

Решение грубой силы.

Сохранено 1 байт благодаря Xnor

f n=[(x,y)|y<-[1..],x<-[1..n],x*x*y==n]!!0
Damien
источник
Хорошее решение, мне нравится, как оно не используется modили div. Я думаю, что вы можете сделать y<-[1..]из-за лени.
xnor
Да ты прав. Это было невозможно с моим первым решением, last[(x,y)|x<-[1..n],y<-[1..n],x*x*y==n]но теперь оно будет работать. Спасибо. У вас есть собственное решение в Haskell?
Дэмиен
1

05AB1E, 14 байтов

Lv¹ynÖi¹yn/y‚ï

Разъяснения

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

Попробуйте онлайн

Emigna
источник
1

Python, 74 байта

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

Достаточно просто.

Backerupper
источник
0

Python 2.7 (без гольфа) - 181 байт

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

Запустить как: е (число) например. е (24)

Образец вывода:

>> 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)
Свадхикар с
источник
1
Пожалуйста,
постарайтесь
0

APL, 25 символов

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

По-английски:

  • 0⍳⍨⌽⍵|⍨×⍨⍳⍵: индекс наибольшего из квадратов до n, который делит полностью n;
  • 1+⍵-: индекс находится в обращенном массиве, поэтому настройте индекс
  • (⊢,⍵÷×⍨): получить результат: сам индекс (a) и частное b (то есть n ÷ a * a)

Тест:

     ↑{(⊢,⍵÷×⍨)⊃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
lstefano
источник
0

JavaScript (ECMAScript 6), 35 байт

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]
l4m2
источник