优化Project euler问题12的意外时间结果

Question

我已经解决了Project Euler问题12，并试图优化我的解决方案
我关注的部分是求除数的部分
我创建的第一个算法我以为会比第二个慢，但事实并非如此，我不明白为什么？

第一个(常规计数直到n**0.5(：

from math import sqrt
def get(n):
count = 0
limit = sqrt(n)
for i in range(1,int(limit)+1):
if n%i==0:
count+=2
if limit.is_integer():
return count-1
return count

第二(素数因子分解，得到每个素数的度数，为了使用这个公式，我使用了素数的形式，你可以在这里看到，它计算得更快，但它仍然更慢(：

def Get_Devisors_Amount(n):#Prime factorization
if n <=1: return 1
dcount = 1
count = 0
while n%2==0:
count+=1
n//=2
dcount*=(count+1)

count = 0
while n%3==0:
count+=1
n//=3
dcount*=(count+1)

i = 1#count for the form of primes 6n+-1
while n!=1:
t = 6*i+1
count = 0
while n%t==0:
count+=1
n//=t
dcount*=(count+1)
t = 6*i-1
count = 0
while n%t==0:
count+=1
n//=t
if count!=0:
dcount*=(count+1)
i+=1
if dcount==1: return 2# n is a prime
return dcount

我如何测试时间

import time
start = time.time()
for i in range(1,1000):
get(i)
print(time.time()-start)

start = time.time()
for i in range(1,1000):
Get_Devisors_Amount(i)
print(time.time()-start)

输出：获取：0.002999835205078125
get_Devisors_Mount:0.009994029998779297

虽然我使用的是属性和公式，我认为应该使搜索时间更低，但第一种方法仍然更快。你能向我解释一下为什么吗？

Answer 1

在第一种方法中，测试从1到sqrt(x)的每个数字的可分割性，因此测试单个数字的复杂性为sqrt(x)。根据这个公式，第一个n根的和可以近似为n*sqrt(n)
方法1的时间复杂度：O(N*sqrt(N))(N是要测试的数字的总数(。

在第二种方法中，有两种情况：

1. 如果一个数不是素数，则测试n之前的所有素数。复杂性-O(n/6) = O(n)
2. 如果一个数是素数，我们可以将复杂度近似为O(log(n))(对于这种情况，可能会有更准确的复杂度计算，我正在进行近似，因为这在证明中无关紧要(

对于素数，利用我们用(n/6)素数测试它们的事实，复杂性将变为5/6 + 7/6 + 11/6 + 13/6 + 17/6 ..... (last prime before n)/6。这可以暂时减少到(sum of all prime numbers till n)/6。现在，到N的所有素数的和可以近似为N^2/(2*logN)。因此，该步骤的复杂度变为CCD_ 14。

方法2的时间复杂度：O(N^2/(12*lognN))(N是被测数字的总数(。

(如果你愿意，你可以为每一步的时间复杂性制定更准确的界限。我做了一些近似，因为它有助于证明这一点，而不会做出任何过于乐观的假设(。

Answer 2

您的第一个算法明智地只考虑高达sqrt(n(的除数。

但是你的第二个算法一直考虑除数，直到n，尽管无可否认，如果n有很多因子，n会在这个过程中减少。

如果你在你的算法中解决了这个问题，通过改变这个：

t = 6*i-1

到此：

t = 6*i-1
if t*t > n:
return dcount * 2

然后你的第二个算法会更快。

(* 2是因为算法最终会找到剩余的素数(n本身(，然后dcount *= (count + 1)会在返回之前加倍计算。(