Project Euler Problem 051

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

 *1290601139*57の第1桁を置き換えることで, 157, 257, 457, 557, 757, 857という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換ることを考えよう.
この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993.
よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

？？？あとで整理します。

import math
import itertools            
import datetime


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


def num2list(n):
    result = []
    while n:
        result.append(n % 10)
        n /= 10
    return result[::-1]
    

def count_digits(n):
    result = [ 0 ] * 10
    while n:
        result[n % 10] += 1
        n /= 10
    return result


def make_numbers(*terms):
    for num in range(10):
        val = 0
        for i in terms:
            val = val * 10 + (num if i == '?' else i)
        yield val


def make_glob(n, digit):
    original  = num2list(n)
    
    a = count_digits(n)
    a[n%10] = 0
    
    replaced = []
    for i, j in enumerate(a):
        if j >= digit:
            replaced.append(i)
    
    candidate = []
    for i in replaced:
        b = []
        for j in xrange(len(original)):
            if i == original[j]:
                b.append(j)
        candidate.append(b)
        
    for p in candidate:
        for k in xrange(digit, len(p)+1):
            for q in itertools.combinations(p, k):
                x = original[:]
                for y in q:
                    x[y] = '?'
                yield x


def euler051():
    primes = primelist(1000000)
    primes = [ i for i in primes if i > 100000 and max(count_digits(i)) >= 2 ]
    setprimes = set(primes)
    
    for i in primes:
        for j in make_glob(i, 2):
            c = sum([ 1 for k in make_numbers(*j) if k in setprimes ])
            if c == 8: return i
            

begin = datetime.datetime.now()
print euler051()                
end = datetime.datetime.now()

print end - begin

答え: 121313
実行時間: 0.756335秒くらい