代码高尔夫：数字的质因数

Question

根据字符数查找素因数的最短方法是什么任意数量？

输入示例：1806046

输出示例：2x11x11x17x439

示例计算器

Answer 1

C#, 69

x 是输入数字

int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};

其中包括：

using system;
namespace nameSP
{
   class Program
   {
     static void Main(string[] args)
     { 
        int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};
     }
   }
}

Answer 2

必填 J 答案（2 个字符）：

q:

Answer 3

ANSI C，79 个字符

main(d,i){for(d+=scanf("%d",&i);i>1;i%d?++d:printf("%d%c",d,(i/=d)>1?'x':10));}

Answer 4

Mathematica（15 个字符，包括括号）：

FactorInteger

示例：

FactorInteger[42]

{{2, 1}, {3, 1}, {7, 1}}

Answer 5

Python：77 个字符，包含输入和输出

d,s,n=2,'',input()
while n>1:
 if n%d:d+=1
 else:s+='%dx'%d;n/=d
print s[:-1]

Answer 6

Haskell，53 个字符：（包括 3 个换行符）

a%1=[]
a%n|mod n a<1=a:p(div n a)|1>0=(a+1)%n
p=(2%)

示例：

*Main> p 1806046
[2,11,11,17,439]

Answer 7

Python（没有 I/O 的 228 个字符，有 I/O 的 340 个字符）：

import sys

def primeFactors(n):
    l = []
    while n > 1:
        for i in xrange(2,n+1):
            if n % i == 0:
                l.append(i)
                n = n // i
                break
    return l if len(l) > 0 else [n]

n = int(sys.argv[1])
print '%d: %s' % (n, 'x'.join(map(lambda x: str(x), primeFactors(n))))

可以压缩到 120 个字符：

import sys
n,l=int(sys.argv[1]),[]
while n>1:
 for i in range(2,n+1):
    if n%i==0:l+=[str(i)];n/=i;break
print'x'.join(l)

注意：这是 if 之前的制表符，而不是四个空格。它作为另一级缩进，只需要一个字符而不是两个字符。

Answer 8

F#

81 chars

let rec f n=if n=1 then[]else let a=[2..n]|>List.find(fun x->n%x=0)in a::f(n/a)

效率非常低，但由于目标无疑是编写尽可能短的代码，所以我忽略了这一点。

可读形式（使用 #light 语法）：

let rec factorise n =
    if n = 1 then [] else
    let a = [2 .. n] |> List.find (fun x -> n % x = 0)
    a :: factorise (n / a)

Answer 9

GNU bc，47 个字符，包括收集输入（需要 print、else 和 read 的 GNU 扩展）：

x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;i}

如果您确实想要输出中的 x 字符，则它是 64 个字符：

x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;print i;if(x>1)"x"}

另外，请注意，使用 bc 允许处理任意长度的数字。

Answer 10

APL 中的 11 个字符

不包括函数头和换行符

factors←{2÷/∪⌽∧\⍵∨⍳⍵}

Answer 11

Erlang，核心为 122 个字符，整个模块为 152 个：

-module(pf).
-export([f/1]).

f(N) -> f(N,2,[]).
f(1,_,L) -> lists:reverse(L);
f(N,P,L) when N rem P == 0 -> f(N div P,P,[P|L]);
f(N,P,L) -> f(N,P+1,L).

从控制台调用：

70> string:join([integer_to_list(X) || X <- pf:f(1806046)], "x").
"2x11x11x17x439"

Answer 12

实际产生指定输出的 Mathematica 答案：

Print@@Riffle[Join@@ConstantArray@@@FactorInteger[n],x]

55 个字符。假设 n 是输入数字，并且 x 没有分配给它的值。

Answer 13

Ruby 39B 71B（通过 STDIN）

#!ruby -nrmathn
p$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"

Answer 14

迄今为止最好的 Perl 答案 - 70 个字符，没有额外的模块（除非您计算 5.10 的特殊功能）：

perl -nE'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a}$,=x;say f$_'

不适用于 1 或 0，但适用于其他一切。如果您不喜欢使用 say，或者使用的是早期版本的 Perl，这里有一个 81 个字符的版本：

perl -ne'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="\n";print f$_'

Answer 15

哇，你们不太擅长优化。我可以在 Perl 中用 63 个字符来完成，如果你坚持在顶部包含 #!/usr/bin/perl，则可以使用 79 个字符：（

use Math::Big::Factors;
@f=factor_wheel($ARGV[0],1);
print @f;

别那样看我。忠诚的程序员很懒 程序员。）

Answer 16

虽然这不是我最好的作品，但这是我在 Haskell 中的答案，83 个字符。

f n = s [2..n] n
s [] _ = []
s (p:z) n = p:s [x | x<-z, mod x p /= 0, mod n x == 0] n

我确信还有更多事情可以做，但目前来说已经很好了。

编辑：重新安排一些东西来削减角色，效率较低，但更小。

Answer 17

Perl，223 个字符

perl -ne'f($o=$_,2);sub f{($v,$f)=@_;$d=$v/$f;if(!($d-int($d))){print"$f ";if(!p($d)){print"$d ";return(0);}else{f($d,$f);}}else{while(p(++$f)){}f($v,$f);}}sub p{for($i=2;$i<=sqrt($_[0]);$i++){if($_[0]%$i==0){return(1);}}}'

Answer 18

VB6/VBA - 190 个字符

Public Function P(N As Long) As String
Dim I As Long, O As String
Do While N > 1: For I = 2 To N
If N Mod I = 0 Then
O = O & " " & I: N = N / I: Exit For: End If: Next: Loop: P = O: End Function

Answer 19

Perl，70 个字符

$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;push@x,$i}print@{$,=x}

Answer 20

Euphoria：106 个字符

procedure f(atom a)atom x=2
loop do
while remainder(a,x)do
x+=1
end while
?x
a/=x
until a=1
end procedure

Answer 21

VB6/VBA - 147 个字符

我不允许留下评论，但可以通过不使用 Option Explicit 来稍微缩短之前的答案。利用 VB6/VBA 的一些更危险的功能，您可以使用以下功能。无需声明变量是什么，如果追求最终的简洁性，也无需将函数声明为公共！如果 End If 位于同一行，则不需要 End If。

Function P(N As Long)
    Dim I, O
    Do While N > 1: For I = 2 To N
    If N Mod I = 0 Then O = O & " " & I: N = N / I: Exit For: 
    Next: Loop: P = O
End Function

这可以通过以下方式进行测试：

Public Sub TestP()
    Dim s: s = P(1806046)
    Debug.Print s
End Sub

Answer 22

Go 编程语言，100 个字符：

package main;func main(){n:=42;c:="x";for i:=2;n>1;i++{if n%i<1{n/=i;if(n<2){c=""};print(i,c);i--}}}

我的程序，具有正确的缩进：

package main

func main() {
 n := 42 // or whichever input number you like
 c := "x" // separating printed integers
 for i:=2 ; n>1; i++ {
  if n%i<1 { // n%i==0
   n /= i
   if(n<2) { c = "" } // n==1
   print(i, c)
   i--
  }
 }
}

Answer 23

74 Python 中的 75 个字符

a=input();b=2
while b*b<=a:
    if a%b==0:print b;a/=b;b=1
    b+=1
print a

源自我的质因数分解 TI-BASIC 代码。

既然我正在谈论 TI-Basic...

TI-Basic 中的 77 个字符

input a
2→b
while b²<a
a/b→c
if int(c)=c:then:disp b:c→a:1→b:end
b+1→b
end
disp a

Answer 24

C# 和 LINQ，241 个字符：

public IEnumerable<int> F(int n)
{
    return Enumerable.Range(2,n-1)
        .Where(x => (n%x)==0 && F(x).Count()==1)
        .Take(1)
        .SelectMany(x => new[]{x}.Concat(F(n/x)))
        .DefaultIfEmpty(n);
}

public string Factor(int n) {
    return F(n).Aggregate("", (s,i) => s+"x"+i).TrimStart('x'); 
}

压缩：

int[] F(int n){return Enumerable.Range(2,n-1).Where(x=>(n%x)==0&&F(x).Length==1).Take(1).SelectMany(x=>new[]{x}.Concat(F(n/x))).DefaultIfEmpty(n).ToArray();}void G(int n){Console.WriteLine(F(n).Aggregate("",(s,i)=>s+"x"+i).TrimStart('x'));}

Answer 25

C#，366 个字符

对于此类事情，C# 并不是最冗长的语言，但它非常紧凑：

class P {
   static void Main(string[] a) {
      int i = int.Parse(a[0]);
      var p = new System.Collections.Generic.List<int>();
      for (int n = 2; i > 1; n++)
         if (p.Find(q => n % q == 0) == 0) {
            p.Add(n);
            while (i % n == 0) {
               System.Console.WriteLine(n);
               i /= n;
            }
         }
   }
}

编辑：
我看到 Noldorin 在他的 F# 代码中使用了 List.Find 方法，并意识到它会比 foreach 短一点...

编辑：
好吧，如果它不必是一个完整的程序...

C#，181 个字符

string f(int i) {
   var r = "";
   var p = new System.Collections.Generic.List<int>();
   for (int n = 2; i > 1; n++)
      if (p.Find(q => n % q == 0) == 0) {
         p.Add(n);
         while (i % n == 0) {
            r += "x" + n;
            i /= n;
         }
      }
   return r.Substring(1);
}

压缩：

string f(int i){var r="";var p=new System.Collections.Generic.List<int>();for(int n=2;i>1;n++)if(p.Find(q=>n%q==0)==0){p.Add(n);while(i%n==0){r+="x"+n;i/=n;}}return r.Substring(1);}

Answer 26

与 Paxinum （Mathematica 答案）类似，这里有一个bash:

$ factor 1806046
1806046: 2 11 11 17 439

7 个字符，排除数字。

Answer 27

Python递归解法

99个字符（含空格）
87 个字符（不含空格）

def f(n,i=2,r=""):
    while n%i<1:r+="%dx"%i;n/=i
    return f(n,i+1,r)if n>1 else r
print f(input())[:-1]

更新：
完全递归版本

def f(n,i=2,x=""): return x if n<2 else f(n,i+1,x)if n%i else f(n/i,i,x+'%dx'%i)
print f(input())[:-1]

对于除最小输入之外的所有输入，这两个版本都容易出现堆栈溢出。

Answer 28

在 PARLANSE 中，这可以解决问题（252 个字符）：

(action (procedure natural)
   (loop 
      (ifthen (== ? 1) (return))
      (do f i 2 ? 1
         (ifthen (== (modulo ? i) 0)
            (print ?)
            (= ? (/ ? i))
            (exit f)
         )ifthen
      )do
    )loop
)action

我确信有一个更小的 APL 程序可以做到这一点。

Answer 29

Javascript，56

f="";
for(i=2;i<n;i++)
    if(n%i==0){
        f+=i+"x";
        n/=i;i--
    }
f+=n;

（54 个字符）

首先声明 n= 要分解的数字（包括 2 个字符），

然后执行代码。

例子：

> n=12345
  12345

> f="";for(i=2;i<n;i++)if(n%i==0){f+=i+"x";n/=i;i--}f+=n
  "3x5x823"

Answer 30

Python 3 163

不打印结果。

l,f,p=len,lambda n:list(filter(lambda b:n%b==0,range(2,n))),lambda n:l(f(n))==0;r=lambda n: n if p(n) else[x if p(x) else r(x) for x in [f(n)[0],f(n)[l(f(n))-1]]]

将其用作函数：

print(r(1806046))