python - 如何在代码中实现除数函数？

Question

总体问题:欧拉计划 12 - 第一个除数超过 500 的三角形数的值是多少？

问题重点:除数函数

语言:Python

描述:我使用的函数是粗鲁的，程序找到一个除数比 x 多的数字所花费的时间几乎呈指数增长，每增加 10 或 20 个数字。我需要达到 500 或更多除数。我已经确定除数函数是占用程序的原因。我所做的研究使我找到了除数函数，特别是 除数函数，它应该是一个计算任何整数的所有除数的函数。我看过的每一页似乎都是针对数学专业的，而我只有高中数学。虽然我确实看到了一些提到素数分配和阿特金斯筛法的页面，但我无法在素数和找到任何整数的所有约数之间建立联系，也无法在网上找到任何关于它的信息。

主要问题:有人可以解释如何编写除数函数的代码甚至提供示例吗？当我用代码看数学概念时，它们对我来说更有意义。非常感谢。

强力除数函数:

def countdiv(a):
    count = 0
    for i in range(1,(a/2)+1):
        if a % i == 0:
            count += 1
    return count + 1    # +1 to account for number itself as a divisor

Answer 1

如果您需要一个强力函数来计算除数(也称为 tau(n))

这是它的样子

def tau(n):
        sqroot,t = int(n**0.5),0
        for factor in range(1,sqroot+1):
                if n % factor == 0:
                        t += 2 # both factor and N/factor
        if sqroot*sqroot == n: t = t - 1 # if sqroot is a factor then we counted it twice, so subtract 1
        return t

第二种方法涉及将 n 分解为其质因数(及其指数)。

tau(n) = (e1+1)(e2+1)....(em+1) 其中 n = p1^e1 * p2^e2 ... . pm^em 和 p1,p2..pm 是素数

更多信息 here

第三种方法更容易理解，就是简单地使用 Sieve 来计算 tau。

def sieve(N):
        t = [0]*(N+1)
        for factor in range(1,N+1):
                for multiple in range(factor,N+1,factor):
                        t[multiple]+=1
        return t[1:]

这是在 ideone 上执行的操作