找出连续有七个“7”的所有 10 位质数 - Python
Finding all the 10-digit prime numbers, that have seven "7" in a row - Python
正如标题中所述，我正在尝试生成所有 10 位质数的列表，这些质数连续 7x7。更准确地说，我的意思是可以写成如下的数字：xxx7777777, xx7777777x, x7777777xx, 7777777xxx.
我的想法是生成所有这些数字的列表，然后检查其中哪个是质数。代码如下：
import time
def GeneratingTable():
A = []
for i in range (1,10):
for j in range (0,10):
for k in range (0,10):
A.append(i*1000000000+j*100000000+k*10000000+7777777)
for i in range (1,10):
for j in range (0,10):
for k in range (1,10):
A.append(i*1000000000+j*100000000+77777770+k)
for i in range (1,10):
for j in range (0,10):
for k in range (1,10):
A.append(i*1000000000+777777700+10*j+k)
for i in range (0,10):
for j in range (0,10):
for k in range (1,10):
A.append(7777777000+i*100+j*10+k)
A = list(set(A)) # I want to get rid of duplicats here
print(len(A))
return A
def ifPrime(n): # Maybe I can use more efficient algorithm?
Prime = 1
i = 2
while i * i <= n:
if n%i == 0:
Prime = 0
break
i += 2
if Prime == 1:
return 1
else:
return 0
def HowMany():
counter = 0
A = GeneratingTable()
for i in range (len(A)):
if ifPrime(A[i]):
print(A[i])
counter += 1
return counter
start = time.clock()
print(HowMany())
end = time.clock()
time = end - start
print(time)
我确定我通过这种方式获得的素数数量很高 - 它是 2115，而我的列表 A 中的元素数量是 3159。是我的函数 "GeneratingTable" 有问题还是正在检查是否数是素数？
您的函数 ifPrime 认为所有奇数都是质数，因为您从 i=2 开始并在每个循环中将其递增 2。因此，您只检查偶数除数。将i=2改为i=3，过滤后得到327条结果。我不确定这是否是正确的答案，但以上至少是问题的一部分。
你的 prime 函数是错误的，它应该将 i 增加 1，而不是 2，或者你遗漏了一些素数。
然后你应该直接添加到 set 而不是在生成 table 时创建列表，这样可以节省内存和 CPU 时间（也正如 Chris 评论的那样，你正在执行循环从 0 或 1 开始，这会让你错过值，我在之前的 post 中忽略了这一点，现在所有索引都从 0 开始）。在这种情况下，您可以使用 set comprehension 进行更多简化，使用 5 个公式可以从 1,0,0 开始索引，并且不要忘记 7777770xx。
（这是通过与 B.M 的协作努力调整为正确的解决方案。答案，效率更高，但一开始也会遗漏案例）
（另请注意，散列整数不会花费太多 CPU 时间，因为通常散列 是 整数本身）
其余的似乎还可以。这是我的修改：
import time
def GeneratingTable():
A = {v for i in range (1,10) for j in range (0,10) for k in range (0,10)
for v in [i*1000000000+j*100000000+k*10000000+7777777,i*1000000000+j*100000000+77777770+k,i*1000000000+777777700+10*j+k,7777777000+i*100+j*10+k,7777777000+j*10+k]}
print(len(A))
return A
def ifPrime(n):
i = 2
while i * i <= n:
if n%i == 0:
return False
i += 1
return True
def check():
return sorted([p for p in GeneratingTable() if ifPrime(p)])
start = time.clock()
x = check()
print(len(x),x)
end = time.clock()
time = end - start
print(time)
结果：
3420
203 [1247777777, 1277777771, 1277777773, 1457777777, 1487777777, 1577777771, 1577777777, 1657777777, 1777777741, 1777777751, 1777777777, 1787777777, 1877777773, 1877777777, 1877777779, 1927777777, 1957777777, 2017777777, 2027777777, 2077777771, 2377777771, 2437777777, 2467777777, 2507777777, 2567777777, 2647777777, 2677777771, 2777777707, 2777777711, 2777777719, 2777777741, 2777777759, 2777777777, 2777777797, 2917777777, 3037777777, 3077777777, 3137777777, 3197777777, 3247777777, 3257777777, 3377777773, 3377777779, 3407777777, 3427777777, 3527777777, 3557777777, 3577777771, 3777777701, 3777777767, 3777777793, 3827777777, 3937777777, 3977777773, 3977777777, 4027777777, 4097777777, 4177777771, 4277777773, 4297777777, 4307777777, 4327777777, 4447777777, 4567777777, 4687777777, 4747777777, 4777777703, 4777777717, 4777777727, 4777777729, 4777777759, 4777777769, 4777777789, 4777777793, 4777777799, 4867777777, 4937777777, 4997777777, 5177777777, 5237777777, 5387777777, 5477777777, 5527777777, 5567777777, 5617777777, 5627777777, 5647777777, 5777777701, 5777777771, 5777777791, 5877777779, 6037777777, 6077777773, 6077777777, 6177777773, 6277777777, 6317777777, 6577777771, 6577777777, 6637777777, 6757777777, 6767777777, 6777777731, 6777777737, 6777777757, 6777777791, 6847777777, 6857777777, 6947777777, 6977777771, 6977777773, 7037777777, 7087777777, 7327777777, 7387777777, 7487777777, 7537777777, 7547777777, 7597777777, 7607777777, 7727777777, 7777777019, 7777777027, 7777777057, 7777777069, 7777777081, 7777777103, 7777777127, 7777777169, 7777777199, 7777777207, 7777777211, 7777777229, 7777777237, 7777777261, 7777777327, 7777777361, 7777777369, 7777777379, 7777777391, 7777777421, 7777777429, 7777777453, 7777777493, 7777777517, 7777777549, 7777777577, 7777777597, 7777777633, 7777777639, 7777777649, 7777777663, 7777777669, 7777777691, 7777777703, 7777777741, 7777777781, 7777777783, 7777777789, 7777777823, 7777777849, 7777777853, 7777777871, 7777777937, 7777777963, 7777777993, 7837777777, 7957777777, 8087777777, 8117777777, 8227777777, 8277777773, 8347777777, 8387777777, 8477777771, 8577777773, 8627777777, 8737777777, 8777777713, 8777777717, 8777777759, 8777777777, 8807777777, 8947777777, 8977777777, 9067777777, 9137777777, 9177777773, 9197777777, 9257777777, 9467777777, 9477777773, 9477777779, 9547777777, 9617777777, 9677777771, 9777777767, 9777777787, 9777777799, 9817777777, 9887777777, 9937777777, 9977777773]
注意：关于isPrime函数的效率：该函数测试1个素数是有效的，但是当你有3000+个素数要测试时，最好预先计算一个素数列表直到sqrt(10**10)（例如使用筛子）并针对这些素数进行测试。计算素数列表是一项努力，但在测试大量素数时做得很好（如 B.M 答案）
一种具有高效工具的方法，Eratosthene Sieve 更复杂：
from itertools import *
def p77():
S=set()
for triple in combinations_with_replacement('0123456789',3):
quadruple=triple+('7777777',)
for perm in permutations(quadruple):
if perm[0]!='0': # ensure 10 digits
s=''.join(perm)
S.add(int(s))
A=np.array(list(S))
[eratosthene][1]=np.arange(10**5) # sqrt(10**10)
for i in range(2,317): # sqrt(10**5)
if eratosthene[i]>0:
eratosthene[i*i::i]=0
little_primes=eratosthene[eratosthene>1]
for p in little_primes:
A=A[A%p>0]
return A
这在 0.1 秒内给出了 203 个质数：( -- for 7777777)
['124--, 12--1, 12--3, 145--, 148--, 15--1, 15--7, ',
'165--, 1--41, 1--51, 1--77, 178--, 18--3, 18--7, ',
'18--9, 192--, 195--, 201--, 202--, 20--1, 23--1, ',
'243--, 246--, 250--, 256--, 264--, 26--1, 2--07, ',
'2--11, 2--19, 2--41, 2--59, 2--77, 2--97, 291--, ',
'303--, 30--7, 313--, 319--, 324--, 325--, 33--3, ',
'33--9, 340--, 342--, 352--, 355--, 35--1, 3--01, ',
'3--67, 3--93, 382--, 393--, 39--3, 39--7, 402--, ',
'409--, 41--1, 42--3, 429--, 430--, 432--, 444--, ',
'456--, 468--, 474--, 4--03, 4--17, 4--27, 4--29, ',
'4--59, 4--69, 4--89, 4--93, 4--99, 486--, 493--, ',
'499--, 51--7, 523--, 538--, 54--7, 552--, 556--, ',
'561--, 562--, 564--, 5--01, 5--71, 5--91, 58--9, ',
'603--, 60--3, 60--7, 61--3, 62--7, 631--, 65--1, ',
'65--7, 663--, 675--, 676--, 6--31, 6--37, 6--57, ',
'6--91, 684--, 685--, 694--, 69--1, 69--3, 703--, ',
'708--, 732--, 738--, 748--, 753--, 754--, 759--, ',
'760--, 772--, --019, --027, --057, --069, --081, ',
'--103, --127, --169, --199, --207, --211, --229, ',
'--237, --261, --327, --361, --369, --379, --391, ',
'--421, --429, --453, --493, --517, --549, --577, ',
'--597, --633, --639, --649, --663, --669, --691, ',
'--703, --741, --781, --783, --789, --823, --849, ',
'--853, --871, --937, --963, --993, 783--, 795--, ',
'808--, 811--, 822--, 82--3, 834--, 838--, 84--1, ',
'85--3, 862--, 873--, 8--13, 8--17, 8--59, 8--77, ',
'880--, 894--, 89--7, 906--, 913--, 91--3, 919--, ',
'925--, 946--, 94--3, 94--9, 954--, 961--, 96--1, ',
'9--67, 9--87, 9--99, 981--, 988--, 993--, 99--3 ]
正如标题中所述，我正在尝试生成所有 10 位质数的列表，这些质数连续 7x7。更准确地说，我的意思是可以写成如下的数字：xxx7777777, xx7777777x, x7777777xx, 7777777xxx.
我的想法是生成所有这些数字的列表，然后检查其中哪个是质数。代码如下：
import time
def GeneratingTable():
A = []
for i in range (1,10):
for j in range (0,10):
for k in range (0,10):
A.append(i*1000000000+j*100000000+k*10000000+7777777)
for i in range (1,10):
for j in range (0,10):
for k in range (1,10):
A.append(i*1000000000+j*100000000+77777770+k)
for i in range (1,10):
for j in range (0,10):
for k in range (1,10):
A.append(i*1000000000+777777700+10*j+k)
for i in range (0,10):
for j in range (0,10):
for k in range (1,10):
A.append(7777777000+i*100+j*10+k)
A = list(set(A)) # I want to get rid of duplicats here
print(len(A))
return A
def ifPrime(n): # Maybe I can use more efficient algorithm?
Prime = 1
i = 2
while i * i <= n:
if n%i == 0:
Prime = 0
break
i += 2
if Prime == 1:
return 1
else:
return 0
def HowMany():
counter = 0
A = GeneratingTable()
for i in range (len(A)):
if ifPrime(A[i]):
print(A[i])
counter += 1
return counter
start = time.clock()
print(HowMany())
end = time.clock()
time = end - start
print(time)
我确定我通过这种方式获得的素数数量很高 - 它是 2115，而我的列表 A 中的元素数量是 3159。是我的函数 "GeneratingTable" 有问题还是正在检查是否数是素数？
您的函数 ifPrime 认为所有奇数都是质数，因为您从 i=2 开始并在每个循环中将其递增 2。因此，您只检查偶数除数。将i=2改为i=3，过滤后得到327条结果。我不确定这是否是正确的答案，但以上至少是问题的一部分。
你的 prime 函数是错误的，它应该将 i 增加 1，而不是 2，或者你遗漏了一些素数。
然后你应该直接添加到 set 而不是在生成 table 时创建列表，这样可以节省内存和 CPU 时间（也正如 Chris 评论的那样，你正在执行循环从 0 或 1 开始，这会让你错过值，我在之前的 post 中忽略了这一点，现在所有索引都从 0 开始）。在这种情况下，您可以使用 set comprehension 进行更多简化，使用 5 个公式可以从 1,0,0 开始索引，并且不要忘记 7777770xx。
（这是通过与 B.M 的协作努力调整为正确的解决方案。答案，效率更高，但一开始也会遗漏案例）
（另请注意，散列整数不会花费太多 CPU 时间，因为通常散列 是 整数本身）
其余的似乎还可以。这是我的修改：
import time
def GeneratingTable():
A = {v for i in range (1,10) for j in range (0,10) for k in range (0,10)
for v in [i*1000000000+j*100000000+k*10000000+7777777,i*1000000000+j*100000000+77777770+k,i*1000000000+777777700+10*j+k,7777777000+i*100+j*10+k,7777777000+j*10+k]}
print(len(A))
return A
def ifPrime(n):
i = 2
while i * i <= n:
if n%i == 0:
return False
i += 1
return True
def check():
return sorted([p for p in GeneratingTable() if ifPrime(p)])
start = time.clock()
x = check()
print(len(x),x)
end = time.clock()
time = end - start
print(time)
结果：
3420 203 [1247777777, 1277777771, 1277777773, 1457777777, 1487777777, 1577777771, 1577777777, 1657777777, 1777777741, 1777777751, 1777777777, 1787777777, 1877777773, 1877777777, 1877777779, 1927777777, 1957777777, 2017777777, 2027777777, 2077777771, 2377777771, 2437777777, 2467777777, 2507777777, 2567777777, 2647777777, 2677777771, 2777777707, 2777777711, 2777777719, 2777777741, 2777777759, 2777777777, 2777777797, 2917777777, 3037777777, 3077777777, 3137777777, 3197777777, 3247777777, 3257777777, 3377777773, 3377777779, 3407777777, 3427777777, 3527777777, 3557777777, 3577777771, 3777777701, 3777777767, 3777777793, 3827777777, 3937777777, 3977777773, 3977777777, 4027777777, 4097777777, 4177777771, 4277777773, 4297777777, 4307777777, 4327777777, 4447777777, 4567777777, 4687777777, 4747777777, 4777777703, 4777777717, 4777777727, 4777777729, 4777777759, 4777777769, 4777777789, 4777777793, 4777777799, 4867777777, 4937777777, 4997777777, 5177777777, 5237777777, 5387777777, 5477777777, 5527777777, 5567777777, 5617777777, 5627777777, 5647777777, 5777777701, 5777777771, 5777777791, 5877777779, 6037777777, 6077777773, 6077777777, 6177777773, 6277777777, 6317777777, 6577777771, 6577777777, 6637777777, 6757777777, 6767777777, 6777777731, 6777777737, 6777777757, 6777777791, 6847777777, 6857777777, 6947777777, 6977777771, 6977777773, 7037777777, 7087777777, 7327777777, 7387777777, 7487777777, 7537777777, 7547777777, 7597777777, 7607777777, 7727777777, 7777777019, 7777777027, 7777777057, 7777777069, 7777777081, 7777777103, 7777777127, 7777777169, 7777777199, 7777777207, 7777777211, 7777777229, 7777777237, 7777777261, 7777777327, 7777777361, 7777777369, 7777777379, 7777777391, 7777777421, 7777777429, 7777777453, 7777777493, 7777777517, 7777777549, 7777777577, 7777777597, 7777777633, 7777777639, 7777777649, 7777777663, 7777777669, 7777777691, 7777777703, 7777777741, 7777777781, 7777777783, 7777777789, 7777777823, 7777777849, 7777777853, 7777777871, 7777777937, 7777777963, 7777777993, 7837777777, 7957777777, 8087777777, 8117777777, 8227777777, 8277777773, 8347777777, 8387777777, 8477777771, 8577777773, 8627777777, 8737777777, 8777777713, 8777777717, 8777777759, 8777777777, 8807777777, 8947777777, 8977777777, 9067777777, 9137777777, 9177777773, 9197777777, 9257777777, 9467777777, 9477777773, 9477777779, 9547777777, 9617777777, 9677777771, 9777777767, 9777777787, 9777777799, 9817777777, 9887777777, 9937777777, 9977777773]
注意：关于isPrime函数的效率：该函数测试1个素数是有效的，但是当你有3000+个素数要测试时，最好预先计算一个素数列表直到sqrt(10**10)（例如使用筛子）并针对这些素数进行测试。计算素数列表是一项努力，但在测试大量素数时做得很好（如 B.M 答案）
一种具有高效工具的方法，Eratosthene Sieve 更复杂：
from itertools import *
def p77():
S=set()
for triple in combinations_with_replacement('0123456789',3):
quadruple=triple+('7777777',)
for perm in permutations(quadruple):
if perm[0]!='0': # ensure 10 digits
s=''.join(perm)
S.add(int(s))
A=np.array(list(S))
[eratosthene][1]=np.arange(10**5) # sqrt(10**10)
for i in range(2,317): # sqrt(10**5)
if eratosthene[i]>0:
eratosthene[i*i::i]=0
little_primes=eratosthene[eratosthene>1]
for p in little_primes:
A=A[A%p>0]
return A
这在 0.1 秒内给出了 203 个质数：( -- for 7777777)
['124--, 12--1, 12--3, 145--, 148--, 15--1, 15--7, ',
'165--, 1--41, 1--51, 1--77, 178--, 18--3, 18--7, ',
'18--9, 192--, 195--, 201--, 202--, 20--1, 23--1, ',
'243--, 246--, 250--, 256--, 264--, 26--1, 2--07, ',
'2--11, 2--19, 2--41, 2--59, 2--77, 2--97, 291--, ',
'303--, 30--7, 313--, 319--, 324--, 325--, 33--3, ',
'33--9, 340--, 342--, 352--, 355--, 35--1, 3--01, ',
'3--67, 3--93, 382--, 393--, 39--3, 39--7, 402--, ',
'409--, 41--1, 42--3, 429--, 430--, 432--, 444--, ',
'456--, 468--, 474--, 4--03, 4--17, 4--27, 4--29, ',
'4--59, 4--69, 4--89, 4--93, 4--99, 486--, 493--, ',
'499--, 51--7, 523--, 538--, 54--7, 552--, 556--, ',
'561--, 562--, 564--, 5--01, 5--71, 5--91, 58--9, ',
'603--, 60--3, 60--7, 61--3, 62--7, 631--, 65--1, ',
'65--7, 663--, 675--, 676--, 6--31, 6--37, 6--57, ',
'6--91, 684--, 685--, 694--, 69--1, 69--3, 703--, ',
'708--, 732--, 738--, 748--, 753--, 754--, 759--, ',
'760--, 772--, --019, --027, --057, --069, --081, ',
'--103, --127, --169, --199, --207, --211, --229, ',
'--237, --261, --327, --361, --369, --379, --391, ',
'--421, --429, --453, --493, --517, --549, --577, ',
'--597, --633, --639, --649, --663, --669, --691, ',
'--703, --741, --781, --783, --789, --823, --849, ',
'--853, --871, --937, --963, --993, 783--, 795--, ',
'808--, 811--, 822--, 82--3, 834--, 838--, 84--1, ',
'85--3, 862--, 873--, 8--13, 8--17, 8--59, 8--77, ',
'880--, 894--, 89--7, 906--, 913--, 91--3, 919--, ',
'925--, 946--, 94--3, 94--9, 954--, 961--, 96--1, ',
'9--67, 9--87, 9--99, 981--, 988--, 993--, 99--3 ]