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

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 are primes

更多信息在这里

第三种方法,更简单易懂,只需使用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中的行动