두 수의 최대 공약수의 소인수 분해를 인쇄합니다 구분 된 단일 공백 ​​(추가 공백 없음).

제목은 모든 것을 말합니다. 2 개의 입력 32 비트 양의 정수 로 소수 인수 형태로 m, n >= 2출력 gcd(m,n)됩니다.

입력

골프에 더 좋은 것은 명령 줄 args 또는 stdin의 1 줄입니다.

산출

지수로 구분 된 단일 공백 ​​(추가 공백 없음). 입력이 상대적으로 소수이면 아무것도 출력하지 않습니다.

예 :

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

$ ./factorize 14 15


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

규칙

  • 인수 분해 또는 GCD에 외부 리소스, 수학 라이브러리 또는 내장 함수를 사용할 수 없습니다. 예 : 자바, 아니 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 찾기). 또한 stdin에서 읽는 대신 다른 답변과 같이 2 개의 정수를 기대하는 함수로 만들어 10 문자를 더 줄일 수 있습니다.

답변

루비- 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

확실히 더 나아질 수는 있지만 첫 번째 것은 나쁘지 않습니다.

답변

파이썬 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`,

통역사

반복

입력 예-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++;}}

(인간 검증) 테스트 하네스가 포함 된 언 골프 (정렬) :

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

답변

dc, 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 초안)-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"