python - python素数分解性能

Question

我对 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

Answer 1

没有看到你用于什么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 倍以上的工作来处理您范围内的大质数。