-
Notifications
You must be signed in to change notification settings - Fork 0
/
_051.py
66 lines (57 loc) · 1.49 KB
/
_051.py
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
54
55
56
57
58
59
60
61
62
63
64
65
66
from utils import digits, digits_to_int
MILLION = 10 ** 6
_numbers = [i for i in range(MILLION + 1)]
_numbers[0] = _numbers[1] = False
_numbers[2] = True
def seive():
primes = []
for n in range(2, MILLION + 1):
if _numbers[n]:
primes.append(n)
p = 2 * n
while p < MILLION + 1:
_numbers[p] = False
p += n
return primes
def lowest_n_digit_number(n):
return 10 ** (n - 1)
primes = seive()
n_primes = len(primes)
def indices_to_replace(n):
N = len(str(n))
indices = []
prev = [[i] for i in range(N)]
x = 0
while x <= N - 1:
curr = []
for p in prev:
for j in range(p[len(p) - 1] + 1, N):
curr.append(p + [j])
indices += prev
prev = curr
x += 1
return indices
def replace_indices(indices, n):
ds = digits(n)
lowest = lowest_n_digit_number(len(ds))
numbers = []
for i in range(10):
for ind in indices:
ds[ind] = i
n = digits_to_int(ds)
if n > lowest:
numbers.append(n)
return numbers
def how_many_prime(numbers):
p, first = 0, -1
for n in numbers:
if _numbers[n]: p += 1
if first == -1 and _numbers[n]: first = n
return p, first
for n in primes:
for indices in indices_to_replace(n):
numbers = replace_indices(indices, n)
p, smallest = how_many_prime(numbers)
if p == 8:
print(smallest)
exit(0)