On wide-output sieves

Abstract

We describe and compare several novel sieve-like methods. They assign values of several functions (i.e., the prime omega functions omega and Omega and the divisor function d) to each natural number in the considered range of integer numbers. We prove that in some cases the algorithms presented have a relatively small computational complexity. A more detailed output is indeed obtained with respect to the original Sieve of Eratosthenes.