Imprime la factorización prima del máximo común divisor de dos números

17

El título lo dice todo. Dos entradas de enteros positivos de 32 bits m, n >= 2, salida gcd(m,n)en forma de factorización prima.

Entrada

Args de línea de comando o 1 línea de stdin bien, lo que sea mejor para el golf.

Salida

Espacio único delimitado con exponentes (sin espacios adicionales). No genera nada si las entradas son relativamente primas.

Ejemplos:

$ ./factorize 96 162
2^1 3^1

$ ./factorize 14 15


$ ./factorize 196 294
2^1 7^2

Reglas

  • No puede utilizar recursos externos, bibliotecas matemáticas o funciones integradas para factorización o GCD. Ejemplos: Java, no java.lang.Math. rubí, no prime_division, perl, no factor, etc.
durron597
fuente
1
¿Qué resultado buscas si gcd(n,m) == 1?
undergroundmonorail
¿Está bien si salgo con una excepción? Me ahorraría unos pocos bytes.
undergroundmonorail
En realidad, he cambiado mi enfoque y no tengo necesidad de salir con una excepción. Sin embargo, otros podrían querer saber.
undergroundmonorail
No salga con una excepción. Salida nada :)
durron597
Técnicamente, q:a+.bo __ q:a+.ben J usa no external resources or math libraries, pero no lo publicaré, ya que está muy lejos del espíritu de la pregunta. Solo pensé en compartirlo aquí.
12ıʇǝɥʇuʎs

Respuestas:

10

Python 3, 255 250 237 226 188 180 150 142 137 136 caracteres

a,b=map(int,input().split())
t,g='',1
while g<a:
 g,p=g+1,0
 if a%g+b%g<1:
  while a%g+b%g<1:a/=g;b/=g;p+=1
  t+='%d^%d '%(g,p)
print(t)

¡Es increíble cuánto podría acortar esto simplemente saltando cosas (como, ya sabes, encontrar el mcd)! También podría reducir 10 caracteres más al hacer de esta una función que espera 2 ints, como algunas otras respuestas, en lugar de leer de stdin.

Tal
fuente
¡Esto es intenso! Estoy aprendiendo mucho viendo tus ediciones y tratando de vencerte jajaja. Sin embargo, creo que podrías tener este (de las respuestas de Python)
Rainbolt
1
Puede guardar 1 personaje cambiando while g<a and g<b:awhile(g<a)*(g<b):
Rainbolt
@Rusher Gracias amigo! Su respuesta es la que me motivó a trabajar más duro en esto :) También el truco que me recomendó inspirado para averiguar los a%g+b%gbits
Tal
No creo que la cláusula else sea necesaria. else:g+=1podría ser g+=1, a menos que me falte algo.
isaacg
@isaacg Parece que tienes razón, ¡gracias!
Tal
8

Rubí 168 117 114 101 100 97

Editar: Después de pensarlo, me di cuenta de que no necesitaba el tamiz ya que la primalidad del factor se cuida en el ciclo de factorización. Además, según lo informado por las respuestas de otros (los de Laindir y Tal son los que lo había visto, aunque parece que otros también lo han hecho), eliminó el cálculo de mcd por separado, ya que eso también ocurre en la factorización.
Edición 2: no es necesario do.
Edición 3: exprimiéndolo más.
Edición 4: Sacó un espacio más.
Edición 5: en uptolugar de each; ?^ == "^"!

a,b=ARGV.map{|i|i.to_i}
2.upto(a){|d|c=0
[c+=1,a/=d,b/=d]while a%d+b%d<1
print d,?^,c," "if c>0}

Salida (igual después de editar):

$ ruby factorize.rb 96 162
2^1 3^1 
$ ruby factorize.rb 14 15

$ ruby factorize.rb 196 294
2^1 7^2 

Ciertamente podría mejorarse, pero no está mal para mi primero.

Restablecer a Monica - notmaynard
fuente
Puede eliminar 4 bytes cambiando map{|i|i.to_i}a map &:to_i. Puede eliminar un quinto byte sin contar la nueva línea al final del archivo; Ruby funciona sin ella.
Kernigh
Además, puede usar en $*lugar de ARGV.
daniero
6

Python 2 - 254 252 196 185 156 151 134 126 121

i=1
a,b=map(int,raw_input().split())
while b:a,b=b,a%b
while~-a:
 i+=1;j=0
 while a%i<1:j+=1;a/=i
 if j:print`i`+'^'+`j`,

Interprete

repl.it

Entrada de ejemplo - stdin

100 50

Ejemplo de salida - stdout

2 ^ 1 5 ^ 2

Perno de lluvia
fuente
1
¿Qué hay de …`a`+'^'+`f.count(a)`…?
Ry-
Bastante limpio, me gusta
qwr
@qwr Gracias. Espero poder entender las otras respuestas de Python con el formato de cadena y afeitar algunos caracteres.
Rainbolt
Cambia f.append(i)por f+=[i]para guardar 5 caracteres.
Nolen Royalty
1
Y ahora no necesita usar f en absoluto: p (¿por qué f=''sigue ahí?)
Nolen Royalty
4

Java - 184 175

Esto está inspirado en la respuesta de @Geobits (y un poco de la respuesta de @ Tal), pero suficiente de eso es diferente que decidí crear mi propia respuesta.

class G{public static void main(String[]a){for(Integer i=1,q,n=i.valueOf(a[0]),m=i.valueOf(a[1]);m>=++i;System.out.print(q>0?i+"^"+q+" ":""))for(q=0;n%i+m%i<1;n/=i,m/=i)q++;}}

Arnés de prueba sin protección (tipo de) con (verificación humana):

class G {
    public static void mainMethod(String[] a) {
        for (Integer i = 1, q, n = i.valueOf(a[0]), m = i.valueOf(a[1]); m >= ++i;
                 System.out.print(q > 0 ? i + "^" + q + " " : ""))
            for (q = 0; n % i + m % i < 1; n /= i, m /= i)
                q++;
    }

    public static void main(String[] a) {
        m(3, 3);
        m(196, 294);
        m(294, 196);
        m(14, 15);
        m(15, 14);
        m(96, 162);
        m(162, 96);
        m(300, 400);
        m(400, 300);
        m(100, 100);
        m(7, 7);
        m(4, 8);
    }

    public static void m(int one, int two) {
        mainMethod(new String[] { String.valueOf(one), String.valueOf(two) });
        System.out.println();
    }
}
durron597
fuente
4

cc, 96 bytes

?sbsa2sf[q]sk[lalf~lblf~szrlz+0<ksbsale1+selsx]ss[lfn[^]Plen[ ]P]sp[0selsxle0<plf1+dsflb!<w]dswx

Lee una línea de entrada estándar. Su salida no termina con una nueva línea. (EDITAR: también genera un espacio adicional después de cada factorización. Algunas de las otras respuestas recortan el espacio, pero esta no).

Ejemplo:

$ echo 301343045 421880263 | dc factorize.dc
1021^1 59029^1 $ 

Código con comentarios:

# dc(1) is a stack language, like Forth. Programs push values on the
# stack, then operate on them. For example, to calculate
#  (2 + 3) * (9 - 4)
# the dc code is
#  [2 3 + 9 4 - *]

# [?] reads a line of input.  We expect two integers >= 2.
# [sb sa] stores the integers in variables.
? sb sa     # a, b = two integers from input

# This program sucks common factors from a and b, looping for
# f = 2, 3, 4, 5, and so on.  This method only sucks prime factors,
# but wastes time when f is not prime.
2 sf        # f = 2

# Code in [...] does not run until the program calls it.

# k = code to break a loop
[
 q           # [q] breaks two levels of [...]
] sk        # k = break

# s = loop to suck factor f from a and b
#  This loop increments e, the exponent for factor f.
#  Please set e = 0 before entering this loop.
[
 # [la lf] puts ( a f ) on the stack.
 # [~] does division and remainder.
             # STACK:
 la lf ~     # ( a/f a%f )
 lb lf ~     # ( a/f a%f b/f b%f )

 # [r] swaps the top two stack values.
 # Hold z = b%f and swap a%f with b/f.
             # STACK:
 sz r lz     # ( a/f b/f a%f b%f )

 # f is a common factor if a%f and b%f are zero.  Because a and b are
 # non-negative, a%f and b%f are zero only if a%f+b%f is zero.
             # STACK:
 +           # ( a/f b/f a%f+b%f )

 # Call k to break loop unless a%f+b%f is zero.  [<k] conditionally
 # calls k if the comparison is true.  Comparisons in dc are
 # backwards, so [3 0 <k] would check 0 < 3.  Because a%f+b%f is never
 # negative, [0 <k] is golf for [0 !=k].
             # STACK:
 0 <k        # ( a/f b/f )

 # f is a common factor, so suck it!
 sb sa       # a = a/f, b = b/f, STACK: ( )
 le 1 + se   # increment e, the exponent for this factor
 ls x        # continue loop, [x] executes s
] ss        # s = loop

# p = code to print "f^e "
[
 # [n] prints a number without a newline.
 # [P] prints a string.
 lf n [^]P
 le n [ ]P

 # DEBUG: Uncomment to print a and b.
 #[(a = ]P la n [, b = ]P lb n [)]P 10P
] sp        # p = print

# w = loop to iterate factors
[
 # Call s loop to suck factor f from a and b, and set exponent e.
 0 se        # e = 0
 ls x        # call s loop

 # DEBUG: Uncomment [c] to clear the stack.  Loop s leaves two junk
 # values ( a/f b/f ) on the stack.  Deleting [c] for code golf saves
 # 1 byte but leaks junk on the stack.
 #c

 # Print "f^e " if 0 < e.  Comparisons in dc are backwards, so
 # [0 le <p] would check e < 0, [le 0 <p] checks 0 < e.
 le 0 <p

 # Increment f.  [d] duplicates top value on stack.
             # STACK:
 lf 1 +      # ( f+1 )
 d           # ( f+1 f+1 )
 sf          # ( f ) as f+1 becomes f

 # Continue loop if b >= f.  This is golf for f <= a and f <= b, as
 # extra iterations of the loop cause no harm.
             # STACK:
 lb          # ( f b )
 !<w         # ( ), continue loop if not b < f
] d sw      # w = loop; STACK: ( w )
x           # enter loop unconditionally; STACK: ( ) at entrance
kernigh
fuente
3

PowerShell - 82

$a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}
Rynant
fuente
Este es corto y fácil de leer. 2..$aCanaliza el rango en un bucle Foreach-Object %{...}. El bucle recoge los valores de if($p){"$_^$p"}.
Kernigh
3

JavaScript (borrador de ECMAScript 6) - 89 caracteres

f=(m,n,i=2,k=0)=>(m%i|n%i?(k?i+'^'+k+' ':'')+(i>m?'':f(m,n,i+1)):f(m/i,n/i,i,k+1)).trim()

Convierte la respuesta original (iterativa), a continuación, en una respuesta recursiva.

Explicación

f=(m,n,i=2,k=0)=>           // A function with arguments m and n and optional arguments
                            // i (defaults to 2) and k (defaults to 0)
  (
    m%i|n%i                 // if i is not a divisor of m or n then:
      ?(k?i+'^'+k+' '       //   if k is non-zero append  "i^k " to the output
         :'')               //   else append nothing
        +(i>m?''            //   if i>m then terminate
             :f(m,n,i+1))   //   else increment i and reset k to 0
      :f(m/i,n/i,i,k+1)     // else divide m and n by i and increment k
  ).trim()                  // finally strip any extra spaces from the output.

Respuesta iterativa: JavaScript (ECMASCript 6) - 108 (o 121) 98 caracteres

Versión 2:

f=(m,n)=>{for(s='',i=1;++i<=m;s+=k?' '+i+'^'+k:'')for(k=0;m%i+n%i<1;k++)m/=i,n/=i;return s.trim()}

Versión 1:

Respondiendo la pregunta como se preguntó originalmente:

f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).join(' ')}

O para cumplir con los cambios de la regla después del hecho:

f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).filter(x=>x).join(' ')}

Explicación

f=(m,n)=>                        // Create a function f with arguments m and n
{
  o=[]                           // Initialise an empty array for the output
  i=2                            // Start with a divisor of 2
  for(;i<=m;)                    // Loop while the divisor is not greater than m
    m%i|n%i                      // Test the bitwise OR of m%i and n%1 (i.e. whether
                                 // at least one is non-zero)
      ?i++                       // If m%i>0 or n%i>0 then increment i
      :(m/=i,                    // Otherwise: divide m by i;
        n/=i,                    //                   n by i;
        o[i]=(o[i]|0)+1);        // and add 1 to the i-th element of o
  return o.map((x,i)=>i+"^"+x)   // finally map the sparse array o to a sparse array
                                 // of the strings (index+"^"+value)
          .filter(x=>x)          // turn sparse array into non-sparse array
          .join(' ')             // then concatenate and return.
}

Salida

f(96,162)
"2^1 3^1"

f(14,15)
""

f(80, 80)
"2^4 5^1"

f(196,294)
"2^1 7^2"
MT0
fuente
Hey puedes intentar probar f(158,237)favor
durron597
Es un espacio delimitado con exponentes (resulta que tiene mucho espacio)" 79^1"
MT0
Bien, las otras soluciones no tienen eso y tampoco el ejemplo. Por favor, arregle :)
durron597
Nada en la pregunta, como se preguntó originalmente, define cuánto espacio en blanco está permitido o no; según lo veo, esto cumple con los requisitos, ya que es un espacio en blanco delimitado con exponentes. Sin embargo, vas a ir y cambiar las reglas ahora, ¿verdad?
MT0
2
Bajo las reglas preexistentes, se podría decir que esta implementación omite el requisito "No generar nada si las entradas son relativamente primas". Todavía parece incorrecto desfigurar el código de golf que salió tan bonito. ¿Qué tan breve puedes hacer una filter()llamada?
Keen
3

Perl 6: 90 caracteres, 94 bytes.

sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for
2..@n[0];$p.pairs.fmt("%d^%d").say}

Algo de golf y comentó:

sub MAIN (*@n) { # accept any number of input numbers as @n
    (
        # $p is a Bag, e.g., it holds the primes and the number of times each was added
        my $p = $p ⊎ $_; # Add the prime to the bag
        @n »/=» $_; # Divide all the input numbers by the prime

        redo # Redo the loop iteration with the same prime, in case
             # the numbers can be divided by it multiple times
    )
    if @n.all %% $_ # Do the above only if all of @n are divisible by $_
    for 2..@n[0];   # Do the above for all numbers from 2 .. @n[0]

    $p.pairs.fmt("%d^%d").say # Print join " ", "$prime^$count"
}

El uso es como:

$ perl6 -e'sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for
2..@n[0];$p.pairs.fmt("%d^%d").say}' 51 153
3^1 17^1
Mouq
fuente
⊎ es un símbolo en perl? No lo sabia.
durron597
@ durron597 Solo Perl 6 :)
Mouq
3

Perl, 144 133 118 114 97 93

($a,$b)=<>=~/\d+/g;for(2..$a){for($n=0;$a%$_+$b%$_<1;$n++,$a/=$_,$b/=$_){}$n&&print"$_^$n ";}

Versión sin golf:

($a,$b)=<>=~/\d+/g;
for(2..$a){
    for($n=0 ; $a%$_+$b%$_<1 ; $n++,$a/=$_,$b/=$_) {}
    $n&&print"$_^$n ";
}

Literalmente, comencé a aprender Perl solo para responder esta pregunta (este es mi primer código Perl), por lo que sospecho que esto se puede reducir aún más.

Tal
fuente
Sí, no he examinado su código de cerca, pero foreachsiempre es sinónimo forde Perl 5, por lo que debería cortar 4 caracteres :)
Mouq
@Mouq Nunca he visto un idioma con tanta redundancia ... gracias :)
Tal
2

Java: 247 241

Realiza un seguimiento de los factores en una matriz y los imprime en un bucle.

Tamaño decente para Java, parece.

class G{public static void main(String[]a){Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1];for(;m>=++i||n>i;){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}}for(i=2;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++);}}

// line breaks below

class G{
    public static void main(String[]a){
        Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1];
        for(;m>=++i||n>i;){
            if(n%i+m%i<1){
                f[i]++;n/=i;m/=i--;
            }
        }
        for(i=1;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++);
    }
}
Geobits
fuente
En realidad, puede dejar las otras variables como int, pierde 4 en el int pero las recupera con new int[-> new Integer[por lo que es un lavado.
durron597
Sí, y obtuve otros tres cambiando n%i<1&&m%i<1a n%i+m%i<1.
Geobits
No necesitas el (). Si n==m, por defecto será de m+1todos modos.
Geobits
2
Puede reemplazarlo m/=i;i=1;con m/=i--;Se ejecutará más rápido también :)
durron597
1
¿Son necesarias las llaves después del primer forbucle?
Ypnypn
2

JavaScript (ECMAScript 5) 170 164 163 113

No pude resistirme a seguir el liderazgo de MT0. Había considerado la recurrencia antes, pero me había parecido demasiado fácil equivocarme. Y realmente lo es. La más mínima variación destruye todo.

Hay un violín para quienes gustan de los violines.

function f(a,b,i,e){return i?a%i|b%i?(e?i+'^'+e+' ':'')+(i>a?'':f(a,b,i+1,0)):f(a/i,b/i,i,e+1):f(a,b,2,0).trim()}

Sin golf:

function f(a,b,i,e){
    return i // Check for factor.
        ?a%i|b%i // Check for indivisibility.
            ?(
                e // Check for exponent.
                    ?i+'^'+e+' ' // Add the current factor to result string.
                    :'' // Omit the current non-factor.
             )+(
                i>a // Check for termination state.
                    ?'' // Stop recursion.
                    :f(a,b,i+1,0) // Go to the next factor.
            )
            :f(a/i,b/i,i,e+1) // Failed indivisibility check. Increment exponent and divide subject values.
        :f(a,b,2,0) // Add default factor and exponent.
        .trim() // Get rid of one extra space that's usually on the end.
}

Versión antigua

function f(a,b){for(var r=[],j=-1,i=2;i<=a;)a%i|b%i?++i:(r[j]&&r[j][0]==i?r[j][1]++:r[++j]=[i,1],a/=i,b/=i);for(j=0;i=r[j];++j)r[j]=i.join('^');return r.join(' ')}

Sin golf:

function f(a,b){
    for(var r=[],j=-1,i=2;i<=a;)
        // We (mis)use conditional expression `?:` instead of `if(){}else{}`.
        a%i|b%i ? // Bitwise OR saves one character over logical OR, where applicable.
             // In the truth case, `i` has become uninteresting. Just move on.
            ++i : // We don't mind hitting composites because their prime factors have already been drained from `a` and `b`.
            (
                r[j]&&r[j][0]==i ? // Check if `i` is already a listed factor.
                    r[j][1]++ : // Increment the exponent count.
                    r[++j]=[i,1], // Otherwise, add a new factor with exponent 1.

                a/=i,b/=i // Drain a used-up factor from `a` and `b`.
            );

    // The real work's done. Now we just format.
    for(j=0; i=r[j]; ++j)
        r[j]=i.join('^'); // Join each factor to its exponent.

    return r.join(' ') // Join all factors into result string.
}

Aquí hay algunas pruebas:

[
    f(4, 12),
    f(80, 80),
    f(96,162),
    f(196,294)
];
Afilado
fuente
Esta función recursiva falló f(301343045, 421880263);probablemente porque mi navegador no me permite recurrir tan profundo. Estúpido Firefox roto!
kernigh
Ciertamente. En la práctica, solo usaría una función recursiva si realmente necesitara algún tipo de pila, como la navegación en árbol u otras estructuras de datos inherentemente recursivas. (Claro, los números pueden tratarse como estructuras de datos recursivas, pero tenemos todo tipo de buenas abstracciones para ayudarnos a ignorar ese hecho.)
Keen
2

GolfScript, 68 bytes

~..),2>*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{`.[~]D\/,(`"^"\++}%" "*

Tenga en cuenta que este enfoque requiere O (b 2 ) tiempo y espacio para los enteros "a" y "b".

A costa de un byte adicional, "solo" O (b) tiempo y espacio son necesarios:

~.),2>31*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{`.[~]D\/,(`"^"\++}%" "*

Cómo funciona

~.        # Interpret the input string (“a” and “b”) and duplicate “b”.
.),2>     # Push the array [ 2 3 4 ... b ].
*$        # Repeat each element b times and sort: [ 2 ... 2 3 ... 3 ... b ... b ]
{         # For each element “d” of the array:
  1$1$%   # Calculate a % d.
  3$2$%   # Calculate b % d.
  +!      # Add and negate.
  {       # If both “a” and “b” are divisible by “d”:
    .@@/  # Calculate a / d.
    @2$/  # Calculate b / d.
    .     # Create a dummy value.
  }*      #
  ;       # Pop the topmost stack element (non-divisor “d” or dummy value).
}/        #
;;]       # Pop “a” and “b” and collect the remaining stack elements in an array.
:|.&      # Save that array in “D” and intersect it with itself to deduplicate it.
{         # For each element “d” of “D”:
  `.[~]   # Push string "d" and array [d].
  D\/,(`  # Split “D” around [d] and take the length minus 1. This count the occurrences.
  "^"\    # Push the string "^" and swap it between "d" and it's number of occurrences.
  ++      # Concatenate the three strings.
}%        # Collect all strings into an array.
]" "*     # Join by spaces.
Dennis
fuente
1

Pitón 3 (123)

Utiliza básicamente la misma estructura que la respuesta de Tal .

a,b=map(int,input().split())
s='';p=1
while p<a:
 c=0;p+=1
 while a%p+b%p<1:a/=p;b/=p;c+=1
 if c:s+='%d^%d '%(p,c)
print(s)

Es suficiente recorrer hasta p = a-1, ya que incrementamos inmediatamente para obtener p = a y a> = min (a, b). Si b> a, no hay daño en probar valores inútiles de p por encima de a.

En 2.X, creo que podríamos ahorrar caracteres mediante la impresión de cada pieza como lo conseguimos en lugar de acumular una cadena: if c:print'%d^%d'%(p,c),. Python 3, desafortunadamente, no parece tener una forma compacta de imprimir sin una nueva línea final.

xnor
fuente
1

PHP, 96

<?php
list(,$a,$b)=$argv;for($s=1;$s++<$a;$c&&print"$s^$c ")for($c=0;1>$a%$s+$b%$s;$a/=$s,$b/=$s)$c++;
mleko
fuente
¡Tenemos casi exactamente el mismo código! Mi única mejora es combinar p=0;g+=1en una línea comenzando gen 1, lo que le permite hacer en g<alugar de hacerlo g<=a. Espero que te guste Python.
xnor
@xnor Extrañé tu código. De hecho, es casi lo mismo. Eliminé mi script de Python. Espero que no me tenga que gustar Python, NECESITO aparatos ortopédicos
mleko
No es necesario eliminar su código, usted mismo lo inventó. También se me ocurrió básicamente el juego como Tal, por lo que parece que esto es exactamente a lo que converge el golf Python.
xnor
1

awk - 115 111 96 85

La nueva versión solo puede manejar una línea de entrada. Gracias a durron597 por señalar que solo necesito asegurarme i <= $1.

{for(i=1;++i<=$1;)for(;$1%i+$2%i==0;f[i]++){$1/=i;$2/=i}$0=z;for(i in f)$i=i"^"f[i]}1

Sin golf:

{
    #skip finding gcd as a separate step, get it from the factors
    for(i = 1; ++i <= $1;) {
        for(;$1 % i == 0 && $2 % i == 0; f[i]++) {
            $1 /= i;
            $2 /= i;
        }
    }
    $0 = "";
    for(i in f) {
        $i = i "^" f[i];
    }
    print;
}

Anteriormente podía tomar pares de números repetidamente

{a=$1;b=$2;for($0=c;a-b;)if(a>b)a-=b;else b-=a;for(i=2;i<=a;i++){for(j=0;a%i==0;j++)a/=i;$0=$0(j?i"^"j" ":c)}}1

Sin golf:

{
    a = $1;
    b = $2;
    $0 = "";
    #rip off Euclid
    for(; a != b;) {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    #but not Eratosthenes
    for(i = 2; i <= a; i++) {
        for(j = 0; a % i == 0; j++) {
            a /= i;
        }
        $0 = $0 (j ? i "^" j " " : "");
    }
    print;
}
laindir
fuente
¿Necesita &&i<=b?
durron597
Bueno, estaré ... tienes razón, no: si i > b, entonces b % i != 0... gracias :)
laindir
Este programa no funciona con awk en OpenBSD 5.5, porque NF=0;no puede eliminar $ 1 y $ 2. La salida de echo 301343045 421880263 | awk -f factorize.awk | sed 's/ */ /g'es 5 7 1021^1 59029^1porque $ 1 es 5 y $ 2 es 7. El sed exprime los espacios adicionales que provienen de la impresión de $ 1022, $ 1023, $ 1024, ..., $ 59028 como cadenas vacías unidas por espacios.
kernigh
Gracias @kernigh, funciona en nawk, mawk y gawk. Verificó dos veces que posix no dice nada acerca de la asignación a NF, y lo reemplazó con$0=z;
laindir
@laindir Ese cambio me arregla el programa. Code golf no requiere que los programas sean portátiles. Afortunadamente $0=z;es el mismo número de personajes que NF=0;. Si $0=z;fuera más largo, te diría que te quedes NF=0;.
kernigh
1

Pip , 41 bytes

No es una respuesta competitiva, ya que el lenguaje es más nuevo que la pregunta. Pero esa marca GolfScript de 68 tenía que bajar.

Fi2,++a{p:0T$|g%i{++pg/:i}Ipx.:i.'^.p.s}x

La salida termina en un espacio; si eso es un problema, la siguiente versión también tiene 41 bytes (incluida la -sbandera):

Fi2,++a{p:0T$|g%i{++pg/:i}IplAE:i.'^.p}l

Formateado, con explicaciones:

F i 2,++a {      For i in range(2,a+1); note ++ used to avoid parentheses in 2,(a+1)
  p:0            p will store the greatest power of i that divides both numbers
  T $+(g%i) {    Loop till the sum of g%i is nonzero, where g is a list initialized
                  from cmdline args
    ++p          As long as g%i is [0 0], increment p...
    g/:i         ...and divide both numbers in g by i
  }
  I p            If p is nonzero, i went into both numbers at least once
    x.:i.'^.p.s  Append i^p and a space to the result
}
x                Print the result

Pip, a diferencia de GolfScript, CJam, et al. es un lenguaje imperativo con operadores infijos; También se inspira en los lenguajes de programación de matriz. Esta tarea muestra muy bien ambos paradigmas en el trabajo.

(Tenga en cuenta que se necesita la confirmación 2015-4-20 para ejecutar esto, ya que solo solucioné un par de errores).

DLosc
fuente
0

Python 2 - 262 bytes

n,m=input(),input()
f=lambda i:set(filter(lambda x:i%x<1,range(1,i+1)))
g=max(f(n)&f(m))
p=[]
while g-1:
 p+=[min(filter(lambda x:x>1 and x%2!=(x==2)and not any(map(lambda y:x%y<1,range(2,x))),f(g)))]
 g/=p[-1]
print ' '.join(`a`+^+`p.count(a)`for a in set(p))

La línea 6 necesita trabajo.

metro subterráneo
fuente
1
¿Qué hay de …`a`+'^'+`f.count(a)`…?
Ry:
No tengo idea de cómo me perdí eso. Dios. Gracias.
undergroundmonorail
0

Groovy: 174 caracteres

Este es un puerto de la solución de Geobits para Groovy 2.2.1:

int i=1, n=args[0]as int, m=args[1]as int;s=n>m?n:m+1;f=new int[s];while(m>=++i||n>i){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}};(s-1).times{y=it+1;x=f[y];print"${x>0?"$y^$x ":""}"}

Aquí está la versión sin golf:

int i = 1, n = args[0] as int, m = args[1] as int

s = n>m?n:m+1
f = new int[s]

while (m>=++i||n>i) {
    if (n%i+m%i<1) {
        f[i]++;n/=i;m/=i--;
    }
}
(s-1).times {
    y=it+1
    x=f[y]
    print"${x>0?"$y^$x ":""}"
}
Michael Easter
fuente
Sorprendido de que haya elegido portar la solución de Geobits en lugar de la mía, ya que la mía es 56 caracteres más corta
durron597
0

R: 139

a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}

Con hendiduras:

a=scan() #Take space-separated numeric input from stdin
q=1:a[1]
n=max(q[!a[1]%%q&!a[2]%%q]) #gcd
m=rep(0,n)
for(i in 2:n){
    while(!n%%i){ #prime factorization
        m[i]=m[i]+1
        n=n/i
        }
    if(m[i])cat(paste0(i,"^",m[i])," ")
    }

Uso:

> a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}
1: 196 294
3: 
Read 2 items
2^1  7^2  
plannapus
fuente