Производительность простого факторинга python

Я относительно новичок в 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

Ответы

Ответ 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 раз больше работы для работы с большими штрихами в вашем диапазоне.