Производительность простого факторинга 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