逆に考えて4つの素数からなる数を生成できないでしょうか。
素数またはそのべきの4つの積を生成すればよいですが、順番に生成することはできないので、ある程度範囲を区切って出てきた数をソートして出力します。
ふるい的な方法より少し速くなりました。
from itertools import ifilter, count, imap, takewhile
import timedef is_prime(n):
for p in ifilter(lambda p: p * p <= n, primes):
if n % p == 0:
return False
return Truedef prime(k):
if k < len(primes):
return primes[k]
else:
l = len(primes)
for p in ifilter(is_prime, count(primes[-1] + 1)):
primes.append(p)
if l == k:
return p
l += 1def calc_limit(k, n):
return reduce(lambda x, y: x * prime(y), range(k, k + n), 1)def gen_composite_core(begin0, end0, k = 0, l0 = 0):
if begin0 < end0:
p = prime(l0)
if k == N:
if begin0 == 1:
yield 1
else:
for l in count(l0):
p = prime(l)
begin = begin0
end = end0
limit = calc_limit(l + 1, N - k - 1)
n = 1
while p * limit < end:
begin = (begin + p - 1) / p
end = (end - 1) / p + 1
n *= p
for m in gen_composite_core(begin, end, k + 1, l + 1):
yield n * m
if n == 1:
breakdef gen_composite():
L = 20000
begin = 1
while True:
a = list(gen_composite_core(begin, begin + L))
a.sort()
for n in a:
yield n
begin += Lt0 = time.clock()
primes = [ 2 ]
N = 4 # number of factors
M = 4 # number of consecution
counter = 0
prev = 0
for n in gen_composite():
if n == prev + 1:
counter += 1
if counter == M:
break
else:
counter = 1
prev = nprint n - M + 1
print time.clock() - t0