Project Euler 47（2）

逆に考えて4つの素数からなる数を生成できないでしょうか。
素数またはそのべきの4つの積を生成すればよいですが、順番に生成することはできないので、ある程度範囲を区切って出てきた数をソートして出力します。
ふるい的な方法より少し速くなりました。

from itertools import ifilter, count, imap, takewhile

import time
def is_prime(n):

    for p in ifilter(lambda p: p * p <= n, primes):

        if n % p == 0:

            return False

    return True
def 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 += 1
def 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:

                    break
def 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 += L
t0 = 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 = n
print n - M + 1

print time.clock() - t0