-
Notifications
You must be signed in to change notification settings - Fork 0
/
p51.py
111 lines (100 loc) · 2.4 KB
/
p51.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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import sys
from math import sqrt
def isPrime(n):
i = 2
while i <= sqrt(n):
if n % i == 0:
return False
i += 1
return True
def replaceDigit(number, positions):
ret = []
i = 0
s = list(str(number))
while i < 10:
for position in positions:
s[position] = str(i)
ret[len(ret):] = [int("".join(s))]
i += 1
return ret
def _subsetOfSizeK(k, n):
if k == 0 or n < k:
yield set()
elif n == k:
yield set(range(n))
else:
for s in _subsetOfSizeK(k-1,n-1):
s.add(n-1)
yield s
for s in _subsetOfSizeK(k,n-1):
yield s
def allindices(string, sub, listindex=[], offset=0):
i = string.find(sub, offset)
while i >= 0:
listindex.append(i)
i = string.find(sub, i + 1)
return listindex
def subsetOfSizeK(k,number):
if k == 0 or len(str(number)) < k:
yield set()
elif len(str(number)) == k:
s = set(list(str(number)))
if len(s) == 1:
yield set(range(len(str(number))))
else:
yield set()
elif k == 1:
for i in range(len(str(number))):
yield set([i])
else:
cs = list(str(number))
for c in set(cs):
indices = allindices(str(number),c,[])
if len(indices) == k:
yield set(indices)
elif len(indices) > k:
#subs = _subsetOfSizeK(k,len(indices))
print(len(indices), c, number)
for sub in _subsetOfSizeK(k,len(indices)):
ss = set()
for s in sub:
ss.add(indices[s])
yield ss
def replaceNDigits(number, n, familySize, ps):
sub = subsetOfSizeK(n,number)
for s in sub:
sys.stdout.write(str(number) + ": " + str(s) + ": ")
nums = replaceDigit(number, s)
c, primes = countPrimes(nums,number,ps)
ps |= primes
if c == familySize:
return familySize, ps
sys.stdout.write("\n")
return 0, ps
def replaceDigits(number,familySize, ps):
n = len(str(number))
i = 1
while i < n:
c, ps = replaceNDigits(number, i, familySize, ps)
if familySize == c:
return familySize, ps
i += 1
return 0, ps
def countPrimes(ps,number,primes):
s = 0
l = len(str(number))
for p in ps:
if l == len(str(p)) and (p in primes or isPrime(p)):
sys.stdout.write(str(p) + ", ")
s += 1
primes.add(p)
return s, primes
def smallestPrimeFamily(n):
i = 3
s = 0
ps = set()
while s != n:
if isPrime(i):
s,ps = replaceDigits(i,n,ps)
i += 2
sys.stdout.write("\n")