Python分解质因数的性能

Question

Python分解质因数的性能

pythonperformancealgorithmprime-factoring

13

我对Python相对较新，对于两个相对简单的代码块的性能感到困惑。第一个函数给定一个素数列表，生成一个数字n的质因数分解。第二个生成数字n的所有因子的列表。我本以为prime_factor（对于相同的n）会比factors快，但事实并非如此。我不是在寻找更好的算法，而是想了解为什么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

- user2869495

1

相关：如何逐行分析Python代码？ - jfs

3

你在哪里定义你提供给prime_factors()函数的primes参数？ - rliu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Peters · Accepted Answer

没有看到你使用的是什么来计算质数（无法运行您的代码），我们只能猜测。

但其中一部分内容是纯数学：在小于n的数中大约有n/log(n)个质数（非常粗略地说），这比sqrt(n)要大得多。因此，当您传递一个质数时，prime_factor(n)将进行更多的工作：在找到第一个质因数（n本身！）之前，它需要通过O(n/log(n))次操作，而factors(n)在O(sqrt(n))次操作后放弃。

这可能非常重要。例如，sqrt(10000)只有100，但小于10000的质数有1229个。因此，prime_factor(n)可能需要做超过10倍的工作来处理您范围内的大质数。