Project Euler Problem 047

http://projecteuler.net/index.php?section=problems&id=47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047

連続する2つの数がそれぞれ2つの異なる素因数を持つのは

  14 = 2 × 7
  15 = 3 × 5 の場合である.

同様に連続する3つの数がそれぞれ3つの異なる素因数を持つのは

  644 = 22 × 7 × 23
  645 = 3 × 5 × 43
  646 = 2 × 17 × 19 の場合である.

連続する4つの数がそれぞれ4つの異なる素因数を持つ場合を考え, 連続する数の中で最小のものを答えよ.

分からなかったので無理くり解いた。すごく時間がかかる。

import math
import itertools
import datetime


def primelist(limit=1000):
    checked = [ True ] * (limit/2)
    result = [2]
    for i in xrange(len(checked)):
        val = i * 2 + 3
        if checked[i]:
            result.append(val)
            j = val + val + val
            while j < limit:
                checked[(j - 3) / 2] = False
                j += val + val
    return result


pl = primelist(10000)
def primefactors(n):
    result = []
    
    limit = math.sqrt(n)
    for i in pl:
        while n % i == 0:
            result.append(i)
            n /= i
        limit = math.sqrt(n)
        if limit > n: break
        
    if n > 1:
        m = pl[-1] + 2
        while n > 1 and m <= limit:
            while n % m:
                m += 2
            else:
                while True:
                    n /= m
                    result.append(m)
                    if n % m: break
                limit = math.sqrt(n)
        else:
            if n != 1:
                result.append(n)
                
    return result



def euler047():
    n = 4
    
    def it():
        for i in itertools.count(2):
            l = primefactors(i)
            if len(set(l)) != n: continue
            yield (i, l)
    
    p = 0    
    c = 1
    
    checked = set()
    for i, l in it():
        
        is_ok = False
        if i - 1 == p:
            b = [ (j, l.count(j)) for j in set(l) ]
            
            is_ok = True
            for j in b:
                if j in checked:
                    is_ok = False
                    break
                else:
                    checked.add(j)
        
        if is_ok:
            c += 1
            if c == n:
                print [ i-j+1 for j in xrange(n,0,-1) ]
                return 
        else:
            if c != 1:
                checked = set()
            c = 1
            
        p = i
        

begin = datetime.datetime.now()
euler047()
end = datetime.datetime.now()
print end - begin

答え: 134043 (134043, 134044, 134045, 134046)
実行時間: 1:12.490829秒くらい