Project Euler 47（1）

Problem 47
2つの素数からなる最初の2つの連続した数は、
14 = 2 × 7
15 = 3 × 5
3つの素数からなる最初の3つの連続した数は、
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
4つの素数からなる最初の4つの連続した数を見つけよ。それらの数の最初は？
http://projecteuler.net/index.php?section=problems&id=47

2から順に素因数分解して素数の数を数えて、4個が4回続くのを待てばよいでしょう（Code1）。

この手の問題は、エラトステネスのふるい的に素因数分解するのが定番ですね（Code2）。ここでは素因数分解の結果は保持せずに、素数の個数だけ数えています。ふるい的処理は1000個ずつに区切って行っています。

# Code1

from itertools import takewhile, count, imap
def gen_prime_candidates():

    yield 2

    yield 3

    n = 5

    while True:

        yield n

        yield n + 2

        n += 6
def calc_exp(n, p):

    e = 0

    while n % p == 0:

        e += 1

        n /= p

    return e, n
def factorize(n):

    f = ()

    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):

        e, n = calc_exp(n, p)

        if e:

            f = f + ( (p, e),)

    

    if n > 1:

        f = f + ( (n, 1),)

    return f
def gen_composite():

    for n, m in imap(lambda n: (n, len(factorize(n))), count(2)):

        yield n, m
def pop_push(t, n):

    if len(t) < M:

        return t + (n,)

    else:

        return t[1:] + (n,)
N = 4   # number of factors

M = 4   # number of consecution

full = (N,) * M

t = ()

for n, t in imap(lambda x: (x[0], pop_push(t, x[1])), gen_composite()):

    if t == full:

        print n - M + 1

        break

# Code2

from itertools import ifilter, count, imap, takewhile
def is_prime(n):

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

        if n % p == 0:

            return False

    return True
def gen_primes():

    for p in primes:

        yield p

    

    for p in ifilter(is_prime, count(primes[-1] + 1)):

        primes.append(p)

        yield p
def div_pow(n, p):

    while n % p == 0:

        n /= p

    return n
def factorize(begin, end):

    L = end - begin

    a = range(begin, end)

    b = [ 0 ] * L

    for p in takewhile(lambda p: p * p < end, gen_primes()):

        for n in xrange( (begin + p - 1) / p * p, end, p):

            k = n - begin

            a[k] = div_pow(a[k], p)

            b[k] += 1

    

    for n in xrange(begin, end):

        k = n - begin

        if a[k] > 1:

            b[k] += 1

    

    return b
def gen_composite():

    L = 1000

    begin = 1

    while True:

        f = factorize(begin, begin + L)

        for k in xrange(L):

            yield k + begin, f[k]

        

        begin += L
def pop_push(t, n):

    if len(t) < M:

        return t + (n,)

    else:

        return t[1:] + (n,)
primes = [ 2 ]

N = 4   # number of factors

M = 4   # number of consecution

full = (N,) * M

t = ()

for n, t in imap(lambda x: (x[0], pop_push(t, x[1])), gen_composite()):

    if t == full:

        print n - M + 1

        break