Find all divisors in a range by sieving

divisors_sieve.py

#!/usr/bin/env python3

''' Find all divisors in a range by sieving

    Written by PM 2Ring 2017.05.03

    Prime GP version
'''

from itertools import product
from functools import lru_cache

def lowest_prime_factors(n):
    s = [[1, i] for i in range(n)]
    for i in range(int(n**0.5), 1, -1):
        t = s[i]
        if t[1] == i:
            j = i
            while j < n:
                s[j : n : j] = [t] * ((n - 1) // j)
                j *= i
                t = t + [j]
    return s

@lru_cache(None)
def divisors(j):
    result = a[j]
    j //= result[-1]
    if j > 1:
        result = [u*v for u, v in product(divisors(j), result)]
        result.sort()
    return result

n = 50
a = lowest_prime_factors(n)

for i in range(2, n):
    t = divisors(i)
    print(f'{i:2}: {t}')