欧拉项目 #12 - 两个代码性能之间的差异

Question

我最近开始学习python，为了熟悉这些概念，我开始解决欧拉问题。我一直在尝试解决Euler的第12个问题，但我的代码运行了很长一段时间(超过10分钟，仍在运行(。我在网上检查并运行了这段代码，令人惊讶的是，它只花了11秒。但我无法理解两者之间的区别。如果有人能帮我理解的区别，我真的很感激

我的代码#1:

from time import time
import math
def divisors(n):
n = int(n)
sqrt = int(math.sqrt(n))
result = sum(2 for i in range(1, sqrt+1) if n%i == 0)
for i in range(1, n+1):
if i**2 == n:
result = result - 1
return result
i = 1
num = 0
a = 0
t = time()
while a < 500:
num = num+i
print(num, i)
i = i+1
a = divisors(num)
print(a)
tt = time() - t
print(tt)

我的代码#2

from time import time
import math
def divisors(n):
n = int(n)
sqrt = int(math.sqrt(n))
for i in range(1, n+1):
result = sum(2
for i in range(1, sqrt+1) if n%i == 0)
if i**2 == n:
result = result - 1
return result
i = 1
num = 0
a = 0
t = time()
while a < 500:
num = num+i
print(num, i)
i = i+1
a = divisors(num)
print(a)
tt = time() - t
print(tt)

耗时11秒的代码：

import math
from time import time
t = time()
def divisors(n):
number_of_factors = 0
for i in range(1, int(math.ceil(math.sqrt(n)))):
if n % i == 0:
number_of_factors +=2
else:
continue
return number_of_factors
x=1
for y in range(2,1000000):
x += y
if divisors(x) >= 500:
print x
break
tt = time()-t
print tt

Answer 1

最好用算法标签来问这个问题。

无论如何，不同之处在于函数除数的实现。

对于divisors(n)，您的代码中该函数的复杂性是O(n(导致这一行的原因： for i in range(1, n+1): 但在第三种代码中，divisors(n)的复杂度是O(sqrt(n((

您可以通过编辑divisors功能来改进您的代码

我的提示：1+2+3+…+n=n*(n+1(/2，它不可能是完全平方。。。