[交流] Euler 工程 第廿九题：有多少不同的项? 已有4人参与

print len(set([a**b for a in xrange(2,101) for b in xrange(2,101)]))

# coding: utf-8

factorsOfA = []

for a in xrange(2, 101):
    u = 2
    n = 0
    x = a
    factors = []
    while u <= a:
        if x % u == 0:
            n += 1
            x /= u
        elif n != 0:
            factors.append([u, n])
            n = 0
        else:
            u += 1
    factorsOfA.append(factors)

result = []
for a in factorsOfA:
    for b in xrange(2, 101):
        s = "*".join(["%d**%d" % (x[0],x[1]*b) for x in a])
        if s not in result:
            result.append(s)
print len(result)

Originally posted by huycwork at 2011-06-18 15:54:04:
你这个效率太低了，乘除次数太多，而且，性能似乎受大数算法拖累。我建议你用Perl评估下大数算法的性能，就我这边看，1000万次的迭代，use bigint和no use bigint差别有几秒之多。

另外，建议你看看这个算法 ...

Originally posted by huycwork at 2011-06-18 18:14:07:
电路板实现的乘除算的是定点数，计算时间接近常数，但目前实现大数算法时多半都用用循环实现的，像加法的大数算法，二进制的补码实现看起来像这样：
[code]
int add(int bs1, int bs2){
        int t, ac = bs ...

Originally posted by huycwork at 2011-06-18 18:36:01:
仿竖式的话其实就是多项式算法嘛，即使优化过也在n~n*n之间，不管怎么看也很浪费了，相比于GPU而言。
如果这么确定，后面除了join之外也没看出来什么耗时的操作了，还有一个麻烦可能是数组的合并操作，append ...