我是python的新手，对两个相对简单的代码块的性能感到困惑。给定素数列表，第一个函数生成数字n的素数分解。第二个生成所有n个因子的列表。我本来prime_factor会比factors（对于相同的n）要快，但是事实并非如此。我不是在寻找更好的算法，而是想了解为什么prime_factor它比这么慢factors。
def prime_factor(n, primes):
prime_factors = []
i = 0
while n != 1:
if n % primes[i] == 0:
factor = primes[i]
prime_factors.append(factor)
n = n // factor
else: i += 1
return prime_factors
import math
def factors(n):
if n == 0: return []
factors = {1, n}
for i in range(2, math.floor(n ** (1/2)) + 1):
if n % i == 0:
factors.add(i)
factors.add(n // i)
return list(factors)
使用timeit模块，
{ i:factors(i) for i in range(1, 10000) } 需要2.5秒
{ i:prime_factor(i, primes) for i in range(1, 10000) } 需要17秒
这令我惊讶。factors检查从1到sqrt（n）的每个数字，而prime_factor仅检查素数。在理解这两个功能的性能特征方面，我将不胜感激。
谢谢
编辑：（响应roliu）这是我的代码，用于生成从2到的素数列表up_to：
def primes_up_to(up_to):
marked = [0] * up_to
value = 3
s = 2
primes = [2]
while value < up_to:
if marked[value] == 0:
primes.append(value)
i = value
while i < up_to:
marked[i] = 1
i += value
value += 2
return primes
在没有看到您的用途的情况下primes，我们不得不猜测（我们无法运行您的代码）。
但这只是数学的很大一部分：n/log(n)素数的数量（非常粗略地讲）小于n，而素数比更大sqrt(n)。因此，当您通过质数时，会prime_factor(n)做更多的工作：它O(n/log(n))在找到第一个质数因子（n本身！）之前先进行运算，而factors(n)在O(sqrt(n))运算后放弃。
这可能非常重要。例如，sqrt(10000)只有100，但是有1229个质数小于10000。因此，prime_factor(n) 您需要做10倍以上的工作来处理您范围内的大质数。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句