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

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

如果你需要一个bruteforce函数来计算除数（也称为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 are primes

更多信息here

第三种方法更简单易懂，就是用筛子计算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的作用

Answer 2

我同意这里提交的另外两个答案，你只需要搜索到数字的平方根。不过，我还有一件事要补充。所提供的解决方案将在合理的时间内为您提供正确的答案。但当问题变得越来越棘手时，你将需要一个更强大的功能。

看看Euler's Totient function。尽管它只是间接地应用于这里，但它在以后的问题中非常有用。另一个相关的概念是Prime Factorization。

改进算法的一个快速方法是找到这个数的素因式分解。在维基百科的文章中，他们以36为例，其主因子分解是2^2*3^2。因此，知道了这一点，你就可以用组合数学来求出36个因子的个数。有了这个，你就不需要计算每一个因子，加上你只需要检查除数2和3就可以了。

Answer 3

当搜索n的除数时，您永远不必搜索超过n数的平方根。每当你发现一个小于sqrt(n)的除数时，只有一个匹配的除数大于根，所以你可以将count增加2（如果你找到n的除数d，那么n/d将是对应的）。

不过，要注意正方形的数字。：）根将是一个除数，当然，它不算两次。