Project Euler 51「素数の桁置換」

問の意味を理解するのに一苦労だったのでほんのり補足書換してます。
結構遅い（2分弱）けど、脳ミソが痛いのでギブアップ。

Problem 51 「素数の桁置換」

2桁の数○3の第1桁を置き換えることで 13, 23, 43, 53, 73, 83という6つの素数が得られる。
56○○3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993.
よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

# memo : 1の位を置き換えても8つの素数が得られることはない

from itertools import count, combinations

def hoge(num):
    checked = []
    for n in count(11, 2):
        if n % 5 == 0 or n in checked: continue
        l = list(str(n))
        for i in range(1, len(l)):
            # 何番目を何個置き換えるかの組み合わせ
            for c in combinations(( j for j in range(len(l)-1) ), i):
                lst_ans = []
                for k in list('0123456789'):
                    # 第1桁を0に置き換えることがないように
                    if c[0] == 0 and k == '0': continue
                    N = replace_and_list2num(l, c, k)
                    checked.append(N)
                    if is_prime(N):
                        lst_ans.append(N)
                    if len(lst_ans) == num:
                        #print(lst_ans)
                        return sorted(lst_ans)[0]

def replace_and_list2num(l, c, num):
    L = list(l) # 参照渡しをしないように
    for i in c: L[i] = num
    return int(''.join(L))

def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    return all(n % i != 0 for i in range(3, int(n ** 0.5) + 1, 2))

print(hoge(8))