# Sieving for factorizations

The sieve of Eratosthenes is normally used to generate prime numbers. But it's almost as easy and almost as efficient to make it generate the sequence of factorizations of all natural numbers: instead of eliminating all multiples of each prime p, add p to the list of factors of all its multiples. An implementation of this (with some more care about handling prime powers) is now in Eratosthenes.py in my PADS library.

As an application, I included in the same file a generator for practical numbers, based on a formula described in the link for testing whether a number is practical given its factorization. Despite being highly composite, practical numbers have a lot of similarities as a sequence to prime numbers; one of those similarities is that this formula is a lot like a sieve. But rather than implement it as a sieve, it seemed easier to use the simpler Eratosthenes sieve to generate the factorizations and then test each factorization independently.

As an application, I included in the same file a generator for practical numbers, based on a formula described in the link for testing whether a number is practical given its factorization. Despite being highly composite, practical numbers have a lot of similarities as a sequence to prime numbers; one of those similarities is that this formula is a lot like a sieve. But rather than implement it as a sieve, it seemed easier to use the simpler Eratosthenes sieve to generate the factorizations and then test each factorization independently.