small factors numbers by sieve and other method timed with decorator

By Tony Veijalainen on Aug 24th, 2011 6:42 pm

Here is simple math program to list number whose all factors are in given set of factors.

I have included my timing decorator, which uses my timestring function, so I included that and imports for decorator in the decorator function, bit against the rules. Of course I could have used also the timeit module.

I have implemented task by using previous results and expanding those and using modified sieve algorithm. For the sieve method you should provide your favorite prime_sieve in module utils or change the name according to your module/function name.

def timing(func):
    import time
    from functools import update_wrapper

    def timestr(t):
        return ( ("%i min %.3f s" % divmod(t, 60)) if t > 60
                else  (("%.3f s" % t) if t > 1
                       else "%.3f ms" % (t * 1000) ) )

    def wrapper(*arg, **kwargs):
        t1 = time.clock()
        res = func(*arg, **kwargs)
        t2 = time.clock()
        print('%s took %s' % (func.__name__, timestr(t2-t1)))
        return res

    return update_wrapper(wrapper, func)

@timing
def small_factor_sieve(limit, factors):
    from utils import prime_sieve
    sieve = [True] * limit
    for i in prime_sieve(limit):
        if i not in factors:
            sieve[i::i] = [False] * (limit//i - ((limit % i) == 0))

    return [n for n, t in enumerate(sieve) if n > 1 and t]


# small factor numbers generator
def small_factors(limit, factors):
    thisfar=set([min(factors)])
    for n in range(min(factors),limit):
        if n in factors or any(not n % f and (n / f in thisfar) for f in factors):
            yield n
            thisfar.add(n)

@timing
def test_small_factors(limit, values):
    return list(small_factors(limit, values))


limit = 2 ** 16  + 1
values = set([2, 3, 5])
result = small_factor_sieve(limit, values)
print('%i values' % len(result))
assert test_small_factors(limit, values)==result

This article has been dead for over three months

You