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

Question

整体问题：Project Euler第12题 - 第一个拥有超过五百个因子的三角形数字是什么？

问题的重点：因子函数

编程语言：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

在寻找一个数字 n 的因数时，其实你只需要查找到这个数字的 平方根 就可以了。每当你找到一个小于 sqrt(n) 的因数时，都会有一个对应的因数大于这个平方根。所以你可以把你的 count 加 2（比如说，如果你找到的因数是 d，那么 n/d 就是它的对应因数）。

不过要注意平方数哦。:) 因为平方根本身就是一个因数，所以它不会被算两次。

Answer 2

我同意这里其他两个回答的观点，你只需要查找到这个数字的平方根就可以了。不过我想补充一点，虽然这些方法能在合理的时间内给你正确答案，但当问题变得更复杂时，你可能需要一个更强大的方法。

可以看看欧拉的φ函数。虽然它在这里的应用不是很直接，但在后面的题目中非常有用。还有一个相关的概念是质因数分解。

一个快速提升你算法的方法是找到这个数字的质因数分解。在维基百科的文章中，他们用36作为例子，36的质因数分解是2^2 * 3^2。知道了这一点，你可以用组合数学的方法来找出36的因数个数。这样，你就不需要逐个计算每个因数，而且只需要检查2和3这两个因数就可以了。

Answer 3

如果你需要一个暴力破解的方法来计算一个数字的因子数量（也叫做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是质数

更多信息可以在 这里 找到

第三种方法更简单易懂，就是用筛法来计算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 上可以看到它的实际运行效果