Vereinfache eine Quadratwurzel

29

nVereinfachen Sie bei einer positiven ganzen Zahl die Quadratwurzel √nin der Form, a√bindem Sie alle quadratischen Faktoren extrahieren. Die Ausgabe a,bsollte positive ganze Zahlen n = a^2 * bmit bmöglichst kleinen Zahlen sein.

Sie können aund bin jeder Reihenfolge in jedem vernünftigen Format ausgeben . Sie dürfen Ausgaben von nicht 1als implizit auslassen .

Die Ausgänge für n=1..36als (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)

Dies sind OEIS A000188 und A007913 .

Verwandte: Eine komplexere Version .

Code-Snippet anzeigen

code-golf math arithmetic xnor
quelle
Wir hatten das schon einmal und das wurde als Duplikat der hier verlinkten Herausforderung geschlossen.
Fehler

Antworten:

13

Gelee , 9 Bytes

ÆE;0d2ZÆẸ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Æ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.
Dennis
quelle
3
In UTF-8 ist dies der Fall, aber Jelly verwendet eine benutzerdefinierte Codepage. Der Byte- Link im Header verweist darauf.
Dennis
Sie schreiben , dass Kommentar viel, vielleicht sollten Sie den Bytes wie deutlicher machen (zum Beispiel: [bytes](link-to-byes) (not UTF-8).
NoOneIsHere
12

PARI / GP, 12 Bytes

n->core(n,1)

coregibt nstandardmäßig den quadratfreien Teil von zurück, aber wenn Sie das zweite Argument-Flag auf 1 setzen, werden beide Teile zurückgegeben. Ausgabereihenfolge ist (b, a)z (n->core(n,1))(12) -> [3, 2].

Sp3000
quelle
11

Python 2, 43 Bytes

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

Teste es auf Ideone .

Dennis
quelle
6

MATL , 12 Bytes

t:U\~f0)GyU/

Probieren Sie es online!

Erläuterung

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
Luis Mendo
quelle
2

Mathematica 34 Bytes

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

Dies besagt, dass alle Eingaben ( #) gemäß den folgenden Regeln ersetzt werden sollen: (1) eine Zahl, a , mal die Quadratwurzel von b , {a, b} und eine Funktion b nach der Potenz dessen, was durch {1, b ersetzt werden soll }. Beachten Sie, dass die Funktion davon ausgeht, dass die Eingabe von der Form sein wird,Sqrt[n] . Bei anderen Eingaben funktioniert dies nicht.

Diese unbenannte Funktion ist für Mathematica ungewöhnlich kryptisch. Es kann etwas klarer dargestellt werden, indem seine vollständige Form gezeigt wird, gefolgt von Ersetzungen der ursprünglichen kürzeren Formen.

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

das ist das gleiche wie

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

und

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

und

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

und

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

und

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

Matlab, 51 Bytes

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

Erläuterung

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
quelle
1

JavaScript (ECMAScript 2016), 40 Byte

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

Grundsätzlich eine JavaScript-Portierung von Dennis 'Python 2-Antwort .

Probieren Sie es auf JSBin .

Hinweis: Es funktioniert nicht im strikten Modus, da kes nirgendwo initialisiert wird. Damit es im strengen Modus funktioniert, sollte k=nin der Schleife auf geändert werden let k=n.

Michał Perłakowski
quelle
1

Haskell, 43> 42 Bytes

Brute-Force-Lösung.

Dank Xnor 1 Byte gespeichert

f n=[(x,y)|y<-[1..],x<-[1..n],x*x*y==n]!!0
Damien
quelle
Schöne Lösung, ich mag, wie es nicht verwendet mododer div. Ich denke, Sie können y<-[1..]aufgrund der Faulheit tun .
Xnor
Ja, du hast recht. Mit meiner ersten Lösung war das nicht möglich, last[(x,y)|x<-[1..n],y<-[1..n],x*x*y==n]aber jetzt wird es funktionieren. Vielen Dank. Haben Sie eine eigene Lösung in Haskell?
Damien
1

05AB1E, 14 Bytes

Lv¹ynÖi¹yn/y‚ï

Erklärt

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

Probieren Sie es online aus

Emigna
quelle
1

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

Einfach genug.

Rückendeckung
quelle
0

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

Ausführen als: e (Nummer) zB. e (24)

Beispielausgabe:

>> 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)
Swadhikar C
quelle
1
Bitte versuchen Golf Ihre Antwort so viel wie möglich, das ist ein Code-Golf
CAIRD coinheringaahing
0

APL, 25 Zeichen

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

Auf Englisch:

  • 0⍳⍨⌽⍵|⍨×⍨⍳⍵: Index des größten der Quadrate bis n, der vollständig n teilt;
  • 1+⍵-: Der Index befindet sich im umgekehrten Array. Passen Sie den Index an
  • (⊢,⍵÷×⍨): Erzeugt das Ergebnis: den Index selbst (a) und den Quotienten b (dh n n a * a)

Prüfung:

     ↑{(⊢,⍵÷×⍨)⊃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
quelle
0

JavaScript (ECMAScript 6), 35 Byte

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
quelle