Название говорит обо всем. Два входных 32-разрядных натуральных числа m, n >= 2, вывод gcd(m,n)в простой форме факторизации.

вход

Аргументы командной строки или 1 строка в порядке, что лучше для гольфа.

Выход

Одиночное пространство, разделенное показателями (без дополнительных пробелов). Ничего не выводить, если входы относительно простые.

Примеры:

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

$ ./factorize 14 15


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

правила

• Вы не можете использовать внешние ресурсы, математические библиотеки или встроенные функции для факторизации или GCD. Примеры: Java, нет java.lang.Math. рубин, нет prime_division, перл, нет factorи т. д.

Питон 3, 255 250 237 226 188 180 150 142 137 136 символов

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)

Удивительно, насколько я мог сократить это, просто пропустив что-то (например, вы нашли gcd)! Также я мог бы уменьшить еще 10 символов, сделав эту функцию ожидающей 2 дюйма, как и некоторые другие ответы, вместо чтения из стандартного ввода.

Рубин - 168 117 114 101 100 97

Изменить: подумав об этом, понял, что мне не нужно сито, так как в цикле факторизации учитывается первостепенное значение фактора. Кроме того, как сообщается в ответах других ( я видел это в laindir и Tal , хотя, похоже, что другие тоже это делали), был удален отдельный расчет gcd, поскольку это также происходит при факторизации.
Редактировать 2: не нужно do.
Редактировать 3: Сжимая его больше.
Изменить 4: Вытащил еще один пробел.
Изменить 5: uptoвместо 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}

Вывод (то же самое после редактирования):

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

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

Конечно, можно сделать лучше, но не плохо для моего первого.

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`,

переводчик

repl.it

Пример ввода - stdin

100 50

Пример вывода - stdout

2 ^ 1 5 ^ 2

Ява - 184 175

Это вдохновлено ответом @Geobits (и небольшим количеством ответа @Tal), но этого достаточно, и я решил создать свой собственный ответ.

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++;}}

Ungolfed (своего рода) с (человеческой проверкой) испытательной оснасткой:

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();
    }
}

постоянный ток, 96 байт

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

Он читает одну строку стандартного ввода. Его вывод не заканчивается новой строкой. (РЕДАКТИРОВАТЬ: он также выводит дополнительный пробел после каждой факторизации. Некоторые другие ответы обрезают пробел, но этот не делает.)

Пример:

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

Код с комментариями:

# 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

PowerShell - 82

$a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}

JavaScript (ECMAScript 6 Draft) - 89 символов

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()

Преобразует исходный (итеративный) ответ ниже в рекурсивный.

объяснение

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.

Повторный ответ: JavaScript (ECMASCript 6) - 108 (или 121) 98 символов

Версия 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()}

Версия 1:

Отвечая на вопрос, как первоначально было задано:

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(' ')}

Или соблюдать правила изменения после факта:

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(' ')}

объяснение

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.
}

Выход

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

f(14,15)
""

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

f(196,294)
"2^1 7^2"

Perl 6: 90 символов, 94 байта

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

Несколько де-гольф и прокомментировал:

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"
}

Использование как:

$ 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

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 ";}

Безголовая версия:

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

Я буквально только начал изучать Perl только для того, чтобы ответить на этот вопрос (это мой первый код на Perl), поэтому я подозреваю, что это может быть продолжено.

Ява: 247 241

Отслеживает факторы в массиве и просто выводит их в цикле.

Приличный размер для Java, кажется.

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++);
    }
}

JavaScript (ECMAScript 5) 170 164 163 113

Я почти не смог устоять перед лидерством МТ0. Раньше я думал о рекурсии, но, казалось, слишком легко все испортить. И это действительно так. Малейшее изменение разрушает все.

Есть скрипка для тех, кто любит скрипки.

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()}

Ungolfed:

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.
}

Старая версия

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(' ')}

Ungolfed:

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.
}

Вот несколько тестов:

[
    f(4, 12),
    f(80, 80),
    f(96,162),
    f(196,294)
];

GolfScript, 68 байт

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

Обратите внимание, что этот подход требует O (b ² ) времени и пространства для целых чисел «a» и «b».

За счет одного дополнительного байта «только» O (b) время и пространство необходимы:

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

Как это устроено

~.        # 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.

Питон 3 (123)

Это использует в основном ту же структуру, что и ответ Тала .

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)

Достаточно выполнить цикл до p = a-1, поскольку мы немедленно увеличиваем, чтобы получить p = a и a> = min (a, b). Если b> a, нет ничего плохого в том, чтобы использовать бесполезные значения p выше a.

В 2.X, я думаю , мы могли бы сохранить символы, печатая каждый кусок , как мы получаем его , а не накапливать строку: if c:print'%d^%d'%(p,c),. К сожалению, в Python 3 нет компактного способа печатать без завершающей строки.

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++;

awk - 115 111 96 85

Новая версия может обрабатывать только одну строку ввода. Спасибо durron597 за указание, что мне нужно только убедиться 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

Ungolfed:

{
    #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;
}

Ранее мог принимать пары чисел неоднократно

{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

Ungolfed:

{
    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;
}

зернышко , 41 байт

Не конкурирующий ответ, так как язык новее, чем вопрос. Но этот показатель GolfScript 68 должен был снизиться.

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

Вывод заканчивается в пробел; если это проблема, следующая версия также 41 байт (включая -sфлаг):

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

Отформатированный, с объяснениями:

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

Пип, в отличие от GolfScript, CJam и соавт. является императивным языком с инфиксными операторами; это также берет вдохновение от языков программирования массива. Эта задача хорошо отображает обе парадигмы на работе.

(Обратите внимание, что для выполнения этого необходим коммит 2015-4-20, так как я только что исправил пару ошибок.)

Python 2 - 262 байта

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

Строка 6 нуждается в работе.

Groovy: 174 символа

Это порт решения Geobits для 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 ":""}"}

Вот негольфированная версия:

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 ":""}"
}

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])," ")}

С отступами:

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])," ")
    }

Использование:

> 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