Sieve of Eratosthenes variant to factor numbers
Author: jxuCreated Jan 8, 2023Updated Oct 30, 2025
Does this sieve variant that computes a full factorization by extracting primes from numbers have a name? It's not as good as the linear sieve but gives the factorization directly. The time complexity is something like (n/2 + n/4 + n/16 + ...) + (n/3 + n/9 + ...) + (n/5 + n/25 + ...) < n (1/2 + 1/3 + 1/4 + 1/5 + ...) which should be O(n log n)
def sieve_factor(n):
fact = [[] for _ in range(n)]
for i in range(2, n):
if fact[i] == []:
j = i
while j <= n:
for k in range(j, n, j):
fact[k].append(i)
j *= i
return fact
print(sieve_factor(11))Source: cp-algorithms/cp-algorithms