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.

104 Views
``````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

@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``````