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

Question

如何以字符计数的最短方式，在任何数字中找到质因数？

示例输入： 1806046

示例输出： 2x11x11x17x439

示例计算器

- Alex

---

我假设你所说的“任何数字”是指可以适合于一个合理大小的变量中的数字，而不是例如1093860897630819876058726938274695238746598327465982374659827346598763... - Guffa

Guffa，我的二进制解决方案将处理那个数字 - 我只是不知道它是否会在宇宙热死之前这样做。 - Jon Bright

Answer 1

C＃，69

x是输入的数字

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

使用 includes ：

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

- Yuriy Faktorovich

---

@Alex，但它根本无法编译。 - Alex B

@Alex B，我刚试了一下，运行正常。你确定你声明了输入变量x吗？ - Yuriy Faktorovich

@Yuriy，它本身无法编译，因此这行不是有效的程序，因此也不是有效的 Code Golf 挑战条目。 - Alex B

@Alex B 看起来这只是为了好玩，但如果你想认真对待并且有如此严格的定义，那就是你的权利。 - Yuriy Faktorovich

@Yuriy 这是代码高尔夫的标准格式，是挑战的一部分，与“我的特权”无关。 - Alex B

Answer 2

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

q:

- Jimmy

---

如果您想要独特的因子，那么使用“~.@q:”吧 :) - ephemient

问题中的例子显示了11作为因子出现了两次。 - Jimmy

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

- Alex B

---

这看起来不像我见过的任何 ANSI C。什么样的 main() 会带两个 int 参数？ - Chris Lutz

啊，这里的诀窍是：你可以将'char **argv'用作int，并且C会接受它。 - Alex B

有点作弊，因为它只是将它们打印出来。 ;) - Noldorin

当我编译并运行时，我意识到了这一点。那太糟糕了。你做这个太可怕了。(我总是喜欢使用C的解决方案击败Python和Perl。) - Chris Lutz

@Noldorin：我认为这个代码高尔夫挑战在输入/输出、库的使用等方面定义不清。我会说我的解决方案符合要求，因为它本身是一个完整的程序，输出格式完全按照示例来处理。 - Alex B

我认为它在说“示例输入：”和“示例输出”时已经表述得很清楚了，并且输出有很好的格式。 - Chris Lutz

Answer 4

Mathematica（包括括号共计15个字符）：

FactorInteger

例子：

FactorInteger[42]

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

- Per Alexandersson

---

现在这才是以正确的方式思考问题。 - peterb

这不符合示例输出：2x11x11x17x439。你可以使用bash factor x。哇喔，只有6个字符！我太牛了!!1! - Justin

@Justin：谢谢，我不知道factor！ - Roberto Bonvallet

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]

- Kenan Banks

Answer 6

Haskell, 53 chars:（包括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]

- sth

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之前有一个制表符，而不是四个空格。它作为另一级缩进工作，只需要一个字符，而不是两个字符的代价。

- Aaron Digulla

---

它不应该是可读的代码高尔夫：函数应该被称为p(n)，并且有很多空格可以从中删除。 - paxdiablo

我会在有人想出少于228个字符的东西时开始优化 ;) - Aaron Digulla

你可以再简化一下代码 - 将 l.append(i) 替换为 l+=[i]，将 n=n//i 替换为 n/=i，而且如果我们只是在计算字符数，也可以将 xrange() 替换为 range()。 - David Webb

实际上，您在范围中的“n + 1”将捕获该数字本身，因此l永远不会为空，对吗？返回l。 - Steve Losh

它与p(1)一起工作。它没有打印任何东西，因为1不是质数（它没有精确的两个不同的除数）：http://en.wikipedia.org/wiki/Prime_number - Steve Losh

Answer 8

APL中的11个字符

不包括函数头和换行符

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

- user1372697

---

如果您喜欢编程竞技，可以去 Code Golf Stack Exchange。 - Gareth

Answer 9

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)

- Noldorin

---

你仍然可以通过不使用前向管道并压缩除数测试来减少4个字符：let rec f n=if n=1 then[]else let a=List.find((%)n>>(=)0)[2..n]in a::f(n/a) - cfern

@cfern：那就编辑进去吧。 - badp

Answer 10

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

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可以处理任意长度的数字。

- Jon Bright