Étant donné deux entiers positifs aet b, produire deux entiers positifs cet dtels que:

• c divise a
• d divise b
• cet dsont co-amorces
• le plus petit multiple commun de cet dest égal au plus petit multiple commun de aet b.

S'il existe plusieurs réponses possibles, vous ne pouvez en générer qu'une ou toutes.

Cas de test:

 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

C'est du code-golf . La réponse la plus courte en octets l'emporte.

Gelée , 21 13 octets

ÆEz®0iṂ$¦€ZÆẸ

Essayez-le en ligne!

Si a = 2 ^A · 3 ^B · 5 ^C ·… et b = 2 ^α · 3 ^β · 5 ^γ ·… , alors nous calculons

• c = 2 ^{A> α? A: 0} · 3 ^{B> β? B: 0} · 5 ^{C> γ? C: 0} ·…

• d = 2 ^{A> α? 0: α} · 3 ^{B> β? 0: β} · 5 ^{C> γ? 0: γ} ·…

Maintenant lcm (c, d) = 2 ^{max (A> α? A: 0, A> α? 0: α)} ·… = 2 ^{max (A, α)} · 3 ^{max (B, β)} ·… = lcm ( un B)

et pgcd (c, d) = 2 ^{min (A> α? A: 0, A> α? 0: α)} ·… = 2 ⁰ · 3 ⁰ · 5 ⁰ · ... = 1 .

En d'autres termes: partir de (c, d) = (a, b) . Ensuite, pour chaque nombre premier, divisez ce nombre tout au long de la factorisation de c ou d : celui qui a le plus petit exposant pour ce nombre premier. (Dans cette implémentation, en cas d'égalité, c perd son exposant.)

Donc, si a = 2250 = 2 ¹ · 3 ² · 5 ³ et b = 360 = 2 ³ · 3 ² · 5 ¹ ,

alors c = 2 ⁰ · 3 ⁰ · 5 ³ = 125 et d = 2 ³ · 3 ² · 5 ⁰ = 72 .

Jonathan Allan a joué un énorme 8 octets! Merci ~

R, 143 139 123 octets

f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")

(Merci à @Giuseppe pour ces 19 octets!)

Avec des indentations, des nouvelles lignes et quelques explications:

f=function(a,b,
           q=1:(a*b)) #Defined as function arguments defaults to avoid having to use curly brackets
    for(i in 1:a)
        for(j in 1:b)
            if(!a%%i + b%%j & #Is a divided by c and b divided by d
               max(q[!i%%q+j%%q])<2 & #Are c and d coprimes
               i*j==min(q[!q%%a+q%%b])) #Is this the same lcm
                   cat(i,j,"\n") #Then print

Cas de test:

> f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")
> f(5,7)
5 7 
> f(12,18)
4 9 
> f(6,15)
2 15 
6 5 
> f(1,1)
1 1 

Husk , 10 octets

→ÖF§-⌋⌉ΠmḊ

Force brute. Prend et renvoie des listes, et fonctionne également pour plus de deux numéros.Essayez-le en ligne!

Explication

→ÖF§-⌋⌉ΠmḊ  Implicit input, say [6,15]
        mḊ  Map divisors: [[1,2,3,6],[1,3,5,15]]
       Π    Cartesian product:[[1,1],[2,1],[1,3],[2,3],[3,1],[1,5],[3,3],[6,1],[1,15],[2,5],[3,5],[6,3],[2,15],[6,5],[3,15],[6,15]]
 Ö          Sort by
  F         reduce by
     ⌉      lcm
   -⌋       minus gcd: [[1,1],[3,3],[2,1],[1,3],[3,1],[6,3],[1,5],[2,3],[6,1],[2,5],[3,15],[1,15],[3,5],[6,15],[2,15],[6,5]]
→           Get last element: [6,5]

Mathematica, 82 octets

#&@@Select[Subsets[Flatten@Divisors[{t=#,r=#2}],{2}],GCD@@#==1&&LCM@@#==t~LCM~r&]&

JavaScript (ES6), 90 84 80 octets

Prend l'entrée dans la syntaxe de curry (a)(b)et retourne un tableau de 2 entiers.

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

Cas de test

let f =

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

console.log(JSON.stringify(f(12)(18))) // [ 4,  9 ]
console.log(JSON.stringify(f(18)(12))) // [ 9,  4 ]
console.log(JSON.stringify(f( 5)( 7))) // [ 5,  7 ]
console.log(JSON.stringify(f( 3)( 6))) // [ 1,  6 ] or [ 3, 2 ]
console.log(JSON.stringify(f( 9)( 9))) // [ 9,  1 ] or [ 1, 9 ]
console.log(JSON.stringify(f( 6)(15))) // [ 2, 15 ] or [ 6, 5 ]
console.log(JSON.stringify(f( 1)( 1))) // [ 1,  1 ]

Comment?

a =>                            // a = first input
  g = (                         // g = recursive function that takes:
    b,                          //   b = second input
    c = 1                       //   c = first output divisor, initially set to 1
  ) =>                          //
    (G = (a, b) =>              // G = function that takes a and b
      b ? G(b, a % b) : a       //     and returns the greatest common divisor
    )(                          // we call it with:
      c,                        //   - c
      d = a * b / G(a, b) / c   //   - d = LCM(a, b) / c = a * b / GCD(a, b) / c
    ) - 1 |                     // if the result is not 1 (i.e. c and d are not coprime)
    a % c |                     // or c does not divide a
    b % d ?                     // or d does not divide b:
      g(b, c + 1)               //   do a recursive call with c + 1
    :                           // else:
      [c, d]                    //   return [c, d], a valid factorization of the LCM

MATL , 17 16 octets

&YFt&X>2:!=*^!Xp

Essayez-le en ligne!

Même méthode que la solution Jelly de Lynn

Cela fait un moment que je n'ai pas utilisé n'importe quel MATL (ou matlab d'ailleurs), de nombreuses améliorations sont probablement possibles.

Haskell ,50 48 47 45 42 octets

(?)=gcd;a!b|c<-div a$a?b=(c*c?b,div b$c?b)

Idée: je l'ai remarqué c*d = a*b/gcd(a,b). Ainsi, l'algorithme effectue deux étapes:

1. Commencez par c' = a/gcd(a,b)et d' = b. Cela répond à toutes les exigences sauf cela c'et d'doit être co-amorcé.
2. Pour les faire co-amorcer, je calcule e = gcd(c',d')puis je règle c = c'*eetd = d'/e . Cela conserve toutes les propriétés (car les facteurs combinés restent les mêmes), mais comme je supprime tous les facteurs partagés d, je crée cet dcoprime.

Dans mon implémentation, c'vient d'être appelé c.

Essayez-le en ligne!

-3 octets grâce à Laikoni

05AB1E , 12 octets

Ñ`âʒ.¿I.¿Q}н

Essayez-le en ligne! ou comme suite de tests

R , 126 octets

function(a,b,g=function(x,y)ifelse(o<-x%%y,g(y,o),y),l=a*b/g(a,b))matrix(c(C<-(1:l)[!l%%1:l],D<-l/C),,2)[g(C,D)<2&!a%%C+b%%D,]

Essayez-le en ligne!

Cela prend une approche différente (et apparemment moins golfique) pour trouver les valeurs que l'autre réponse R .

Explication:

function(a,b){
 G <- function(x,y)ifelse(o<-x%%y,G(y,o),y) #gcd function, vectorized for x,y
 l <- a*b/g(a,b)                            #lcm of a,b
 C <- (1:l)[!l%%1:l]                        #divisors of l
 D <- l/C                                   #l/C is the other half of the pair
 rel_prime <- G(C, D) < 2                   #pairs where C,D are relatively prime, lol, GCD
 a_div <- !a%%C                             #divisors of a
 b_div <- !b%%D                             #divisors of b
 C <- C[rel_prime & a_div & b_div]
 D <- D[rel_prime & a_div & b_div]          #filter out the bad pairs
 matrix(c(C,D),,ncol = 2)                   #matrix of pairs, returned
}

sauf que je chausse toutes les définitions comme arguments par défaut et fais tous les calculs sur une seule ligne pour le golfe.

J , 19 octets

(*/:"1)&.|:&.(_&q:)

Essayez-le en ligne!

Basé sur la solution de @ Lynn .

Explication

(*/:"1)&.|:&.(_&q:)  Input: [a, b]
              _&q:   Get exponenets of each prime
         |:&         Transpose
  /:"1 &             Grade each row
 *                   Multiply elementwise
       &.|:          Transpose
           &. _&q:   Convert exponents back to numbers

Haskell , 91 74 octets

a!b=[(x,y)|x<-[1..a],y<-[1..b],rem a x+rem b y+gcd x y<2,lcm a b==lcm x y]

Essayez-le en ligne!

17 octets enregistrés grâce à Laikoni

Python 2 , 75 octets

def f(x):n=1;exec'n+=1;j=k=1\nwhile x[j]%k<1:k*=n**j;j^=1\nx[j]/=k/n;'*x[0]

L'entrée est considérée comme une liste, que la fonction modifie sur place.

Essayez-le en ligne!

Python 3 , 129 octets

lambda a,b:[[c,d]for c in range(1,-~a)for d in range(1,-~b)if((gcd(c,d)<2)*a*b/gcd(a,b)==c*d/gcd(c,d))>a%c+b%d]
from math import*

Essayez-le en ligne! ou Essayez la suite de tests.

Affiche toutes les combinaisons possibles sous la forme d'une liste imbriquée.

Gelée ,  19 15  14 octets

-4 avec pointeur de Leaky Nun (utilisez le diviseur intégré)

^{Je suis presque sûr à 100% que ce n'est pas la façon de le faire, mais voici une première tentative.
Voyons voir qui le surpasse avec un sept ou huit octets!
Oui ... voir la réponse de Lynn avec explication!}

g/־l/
ÆDp/ÇÐṂ

Un lien monadique reprenant une liste des deux nombres et renvoyant une liste de listes des possibilités.

Essayez-le en ligne!

Comment?

g/־l/  - Link: gcd divided by lcm: list [x, y]
g/      - reduce by gcd = gcd(x, y)
   æl/  - reduce by lcm = lcm(x,y)
  ÷     - divide

ÆDp/ÇÐṂ - Main link: list [a, b]    e.g. [160, 90]
ÆD      - divisors (vectorises)          [[1,2,4,5,8,10,16,20,32,40,80,160],[1,2,3,5,6,9,10,15,18,30,45,90]]
  p/    - reduce by Cartesian product    [[1,1],[1,2],...,[1,90],[2,1],[2,2],...,[2,90],....,[160,90]]
     ÐṂ - entries for which this is minimal:
    Ç   -   call the last link (1) as a monad

Perl 6 , 72 octets

{([X] map {grep $_%%*,1..$_},@^a).grep:{([lcm] @a)==([lcm] $_)==[*] $_}}

Essayez-le en ligne!

Prend une liste (a, b). Renvoie une liste de toutes les listes possibles (c, d).

Explication:

-> @ab {
    # Generate all pairs (c, d)
    ([X]
         # where c divides a and d divides b.
         map { grep $_%%*, 1..$_ }, @ab)
    # Only keep pairs with lcm(a, b) = lcm(c, d) and lcm(c, d) = c * d.
    # The latter implies gcd(c, d) = 1.
    .grep: { ([lcm] @ab) == ([lcm] $_) == [*] $_ }
}

Python 2 , 126 121 octets

def f(a,b):
 c=[1,1];p=2
 while p<=a*b:
	t=m=1
	while(a*b)%p<1:m*=p;t=b%p<1;a/=p**(a%p<1);b/=p**t
	p+=1;c[t]*=m
 return c

Essayez-le en ligne!

Python 2 + sympy , 148 octets

from sympy import*
a,b=input()
c=d=z=1
while(a/c*c+b/d*d<a+b)+gcd(c,d)-1+(lcm(c,d)!=lcm(a,b)):E=c==d==z;Q=c==z;d=+E or Q+d;c=+Q or-~c;z+=E
print c,d

Essayez-le en ligne!

-1 merci à Jonathan Frech .

Cette réponse fonctionne en Python 2 (pas Python 3), en utilisant sympy.gcdet sympy.lcmau lieu de math.gcdet math.lcmqui ne sont disponibles qu'en Python 3. Et oui, c'est de la force brute :)

Gelée , 13 octets

Ụ€’×
ÆEz0ÇZÆẸ

Essayez-le en ligne! Ma première réponse Jelly! Edit: ÆEz0µỤ€’×µZÆẸfonctionne également pour 13 octets. Explication:

ÆE              Get prime factor exponents of both values (vectorises)
  z0            Zip but fill the shorter array with 0
    µ           New monadic link
     Ụ€         Grade up each pair (1-indexed)
       ’        Convert to 0-indexing (vectorises)
        ×       Multiply each pair by its grade (vectorises)
         µ      New monadic link
          Z     Zip back into separate lists of prime factor exponents
           ÆẸ   Turn prime exponent lists back into values (vectorises)

PARI / GP, 86 octets

Cela fait juste ce que Lynn dit dans sa réponse:

f(a,b)=forprime(p=2,a*b,v=valuation(a,p);w=valuation(b,p);if(w<v,b/=p^w,a/=p^v));[a,b]

Si je ne compte pas la f(a,b)=partie, c'est 79 octets.

05AB1E , 32 26 24 22 20 19 octets

Ó0ζεD`›0sǝ}øεā<ØsmP

Essayez-le en ligne! Je ne sais toujours pas comment écrire dans cette langue, mais au moins ce n'est pas un algorithme de force brute. Explication:

Ó                       Get exponents of prime factors (vectorised)
 0ζ                     Zip, filling with 0
   ε      }             For each prime
    D`                  Extract the pair of exponents
      ›0sǝ              Overwrite the smaller with 0
           ø            Zip back into two lists of prime exponents
            ε           For each list (} implied)
             ā<Ø        Get a list of primes
                sm      Raise each prime to the exponent
                  P     Take the product