projecteuler/python/p051.py at master · sivapvarma/projecteuler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from euler import sieve_eratosthenes
from itertools import combinations


primes = []
digits = list(map(str, range(10)))
primes_set = set()

def no_of_digits(n):
    return len(str(n))

def prime_digit_replacements(p, n):
    res = 0
    # we don't replace the last digit
    for t in combinations(list(range(no_of_digits(p-1))), n):
        tmp = 0
        for i, d in enumerate(digits):
            lis = [x for x in str(p)]
            for idx in t:
                lis[idx] = d
            temp = int( ''.join(lis) )
            if temp in primes_set:
                tmp += 1
            # early termination already lost more than 2 replacements
            if i+1-tmp > 2:
                break
        if tmp > res:
            res = tmp
    return res


def solve():
    lim = 10**6
    global primes
    primes = sieve_eratosthenes(lim)
    primes = [p for p in primes if len(str(p)) > 4]
    global primes_set
    primes_set = set(primes)
    print('test: %d' % prime_digit_replacements(56003, 2))
    for p in primes:
        d = no_of_digits(p)
        s = str(p)
        if d > 4 and (s.count('0')==3 or s.count('1')==3 or s.count('2')==3):
            print('%d : %d' % (d, p))
            if prime_digit_replacements(p, 3) == 8:
                print('PE51 Ans: %d' % p)
                return None


if __name__ == '__main__':
    solve()
    # for t in combinations(range(4), 3):
    #     print(''.join(map(str, t)))