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)

python
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