Geben Sie bei zwei positiven Ganzzahlen a
und b
zwei positive Ganzzahlen aus, c
und zwar d
so, dass:
c
teilta
d
teiltb
c
undd
sind Co-Prime- Das kleinste gemeinsame Vielfache von
c
und istd
gleich dem kleinsten gemeinsamen Vielfachen vona
undb
.
Wenn es mehr als eine mögliche Antwort gibt, können Sie nur eine oder alle Antworten ausgeben.
Testfälle:
a b c d
12 18 4 9
18 12 9 4
5 7 5 7
3 6 1 6 or 3 2
9 9 9 1 or 1 9
6 15 2 15 or 6 5
1 1 1 1
Das ist Code-Golf . Kürzeste Antwort in Bytes gewinnt.
code-golf
arithmetic
number-theory
Undichte Nonne
quelle
quelle
d
teiltb
Antworten:
Jelly ,
2113 BytesProbieren Sie es online!
Mit anderen Worten: Beginnen Sie mit (c, d) = (a, b) . Teilen Sie dann für jede Primzahl diese Primzahl ganz aus der Faktorisierung von c oder d heraus : je nachdem, welcher Wert den kleinsten Exponenten für diese Primzahl hat. (In dieser Implementierung verliert c bei einem Gleichstand seinen Exponenten.)
Also, wenn a = 2250 = 2 1 · 3 2 · 5 3 und b = 360 = 2 3 · 3 2 · 5 1 ,
dann ist c = 2 0 · 3 0 · 5 3 = 125 und d = 2 3 · 3 2 · 5 0 = 72 .
Jonathan Allan hat satte 8 Bytes Golf gespielt! Vielen Dank ~
quelle
ÆEZ×Ụ’$€$ZÆẸ
[1,18]
nach[15,18]
. Die ursprüngliche Version gab die richtige Antwort zurück ([5,18]
).ÆEz®0iṂ$¦€ZÆẸ
sollte den Trick für 13 tun.R
143139123 Bytes(Danke an @ Giuseppe für diese 19 Bytes!)
Mit Einrückungen, Zeilenumbrüchen und einigen Erläuterungen:
Testfälle:
quelle
!
hat eine höhere Priorität als&
und,|
aber eine niedrigere als+
und*
; Sie sollten in der Lage sein, ein paar Bytes auf diese Weise abzuspielen. dh!i%%q&j%%q
sollte gleichbedeutend sein mit!i%%q+j%%q
GCD(c,d)==1
, dannLCM(c,d)==c*d
. So können wir testenGCD(c,d)==1
und dann überprüfen, ob es sich beic*d==a*b/GCD(a,b)
letzterem umLCM(a,b)
...a*b/GCD(a,b)
nicht kürzer ist alsLCM(a,b)
).Schale , 10 Bytes
Rohe Gewalt. Nimmt Listen auf und gibt sie zurück und funktioniert auch für mehr als zwei Zahlen. Probieren Sie es online!
Erläuterung
quelle
Mathematica, 82 Bytes
quelle
Select[...][[1]]
verwendenFirst@Select[...]
, um ein Byte zu speichern?#&@@
anstatt[[1]]
ein , mehr zu sparen ;-)JavaScript (ES6),
908480 BytesÜbernimmt Eingaben in der Currying-Syntax
(a)(b)
und gibt ein Array mit 2 Ganzzahlen zurück.Testfälle
Code-Snippet anzeigen
Wie?
quelle
MATL ,
1716 BytesProbieren Sie es online!
Gleiche Methode wie Lynn's Jelly-Lösung
Es ist schon eine Weile her, dass ich MATL (oder Matlab für diese Angelegenheit) verwendet habe, so dass wahrscheinlich viele Verbesserungen möglich sind.
quelle
Haskell ,
5048474542 BytesIdee: Mir ist das aufgefallen
c*d = a*b/gcd(a,b)
. Der Algorithmus führt also zwei Schritte aus:c' = a/gcd(a,b)
undd' = b
. Dies erfüllt alle Anforderungen mit Ausnahme dieserc'
undd'
muss Co-Prime sein.e = gcd(c',d')
und setzec = c'*e
undd = d'/e
. Dies behält alle Eigenschaften bei (da die kombinierten Faktoren gleich bleiben), aber da ich alle gemeinsamen Faktoren von entferned
, mache ichc
undd
koprime.In meiner Implementierung
c'
heißt das nurc
.Probieren Sie es online!
-3 Bytes dank Laikoni
quelle
c
spart 3 Bytes: Probieren Sie es online aus!05AB1E , 12 Bytes
Probieren Sie es online! oder als Testsuite
quelle
R , 126 Bytes
Probieren Sie es online!
Dies erfordert einen anderen (und anscheinend weniger golferischen) Ansatz zum Finden der Werte als die andere R-Antwort .
Erläuterung:
mit der Ausnahme, dass ich alle Definitionen als Standardargumente aufgeschlüsselt und alle Berechnungen für die Golfiness in einer Zeile ausgeführt habe.
quelle
J , 19 Bytes
Probieren Sie es online!
Basierend auf @Lynns Lösung .
Erläuterung
quelle
Haskell ,
9174 BytesProbieren Sie es online!
Gespeichert 17 Bytes dank Laikoni
quelle
u*v`div`gcd u v
Speichert ein Byte.lcm
Funktion nicht zu verwenden ?rem a x+rem b y+gcd x y<2
funktionieren.lcm
existiert.rem a x+rem b y+gcd x y<2
funktioniert, und ich frage mich, obrem a x+rem b y+gcd x y+lcm a b-lcm x y<2
funktioniert. Es gibt vielleicht eine (mathematische) Garantie dafürlcm a b>=lcm x y
.lcm a b>=lcm x y
weil 1.x=x1*...*xi
(Primzerlegung)y=y1*...yj
,lcm x y=z1*...*zk
woz1,...,zk
gemeinsam sindx1,...,xi
undy1,...,yj
. 2.a=u1*...*um*x1*...*xi
(Primzerlegung)b=v1*...vn*y1*...yj
,lcm a b=t1*...*tl
diet1,...,tl
gemeinsam ist,u1*...*um*x1*...*xi
undv1*...vn*y1*...yj
. Es ist offensichtlich , dasst1,...,tl
enthältz1,...,zk
, solcm a b>=lcm x y
. Dies ist jedoch nicht nützlich, um die Bedingung als Summe zu schreiben.Python 2 , 75 Bytes
Die Eingabe wird als Liste genommen, die die Funktion an Ort und Stelle ändert.
Probieren Sie es online!
quelle
Python 3 , 129 Bytes
Probieren Sie es online! oder Probieren Sie die Testsuite aus.
Gibt alle möglichen Kombinationen in Form einer verschachtelten Liste aus.
quelle
-~a
und-~b
können einfach umgeschrieben werdena+1
undb+1
zur besseren Lesbarkeit: PJelly ,
19 1514 Bytes-4 mit Zeiger von Leaky Nun (Divisor eingebaut verwenden)
Ich bin fast zu 100% sicher, dass dies nicht der richtige Weg ist, aber hier ist ein erster Versuch.
Mal sehen, wer es mit einem Sieben- oder Acht-Byte übertrifft!
Ja ... siehe Lynns Antwort mit Erklärung!
Ein monadischer Link, der eine Liste der beiden Zahlen erstellt und eine Liste der Möglichkeiten zurückgibt.
Probieren Sie es online!
Wie?
quelle
ÆD
aber (Achselzucken) Gehirn offensichtlich nicht in Gang ...Perl 6 , 72 Bytes
Probieren Sie es online!
Nimmt eine Liste (a, b). Gibt eine Liste aller möglichen Listen zurück (c, d).
Erläuterung:
quelle
Python 2 ,
126121 BytesProbieren Sie es online!
quelle
Python 2 + Sympy , 148 Bytes
Probieren Sie es online!
-1 Danke an Jonathan Frech .
Diese Antwort funktioniert in Python 2 (nicht in Python 3) mit
sympy.gcd
undsympy.lcm
anstelle vonmath.gcd
und,math.lcm
die nur in Python 3 verfügbar sind. Und ja, das ist Brute Force :)quelle
Q=c==z;
(7 Bytes) zu Beginn der while - Schleife und Ersetzenor(c==z)+d
mitor Q+d
(-4 Bytes) undc=+(c==z)or
mitc=+Q or
(-4 Bytes). ( TIO )+
Operator ind=+E
oderc=+(c==z)
, um einen Booleschen Wert in eine Ganzzahl umzuwandeln?True
undFalse
anstelle von1
und0
in Sympy verwenden können.+...
irgendeinen Nutzen hat.Jelly , 13 Bytes
Probieren Sie es online! Meine erste Gelee Antwort! Bearbeiten: Funktioniert
ÆEz0µỤ€’×µZÆẸ
auch für 13 Bytes. Erläuterung:quelle
PARI / GP, 86 Bytes
Das macht genau das, was Lynn in ihrer Antwort sagt:
Wenn ich den
f(a,b)=
Teil nicht zähle , sind es 79 Bytes.quelle
05AB1E ,
322624222019 BytesProbieren Sie es online! Ich habe noch keine Ahnung, wie man in dieser Sprache schreibt, aber es ist zumindest kein Brute-Force-Algorithmus. Erläuterung:
quelle