查找具有七个"7"的所有10位素数.连续-Python [英] Finding all the 10-digit prime numbers, that have seven "7" in a row - Python
问题描述
因此正如标题中所述，我试图生成所有10位素数的列表，它们连续有7x7.更准确地说，我的意思是可以写成如下数字:xxx7777777，xx7777777x，x7777777xx，7777777xxx.
我的想法是生成所有这些数字的列表，然后检查其中哪个是质数.代码如下:
导入时间def GeneratingTable():A = []对于范围在(1,10)中的我:对于范围(0,10)中的j:对于范围(0,10)中的k:追加(i * 1000000000 + j * 100000000 + k * 10000000 + 7777777)对于范围在(1,10)中的我:对于范围(0,10)中的j:对于范围在(1,10)中的k:追加(i * 1000000000 + j * 100000000 + 77777770 + k)对于范围在(1,10)中的我:对于范围内的 j (0,10):对于范围在(1,10)中的k:A.追加(i * 1000000000 + 777777700 + 10 * j + k)对于范围在(0,10)中的我:对于范围(0,10)中的j:对于范围在(1,10)中的k:附录(7777777000 + i * 100 + j * 10 + k)A = list(set(A))#我想在这里消除重复打印(len(A))返回Adef ifPrime(n):#也许我可以使用更高效的算法?素数= 1我= 2当我*我< = n:如果n％i == 0:素数= 0休息我+ = 2如果Prime == 1:返回1别的:返回0def HowMany():计数器= 0A =生成表()对于范围内的我(len(A)):如果ifPrime(A [i]):打印(A [i])计数器 += 1退货柜台开始= time.clock()打印(HowMany())结束= time.clock()时间=结束-开始打印(时间) 我确定以这种方式得到的质数很高-它是2115，列表A中的元素数是3159.我的函数"GeneratingTable"是否有问题或检查该数是否为质数?
您的素数函数是错误的，它应将 i 增加1，而不是2，或者您缺少一些素数.
然后，您应该直接将其添加到 set 中，而不是在生成表时创建列表，这样可以节省内存&CPU时间(也正如Chris所评论的那样，您正在执行从0或1开始的循环，这会使您错过值，我在上一篇文章中忽略了这一点，现在所有索引都从0开始).在这种情况下，您可以使用 set comprehension 进一步简化操作，其中包含5个公式，这些公式可以从1,0,0开始索引，而不要忘记 7777770xx 的索引.
(通过与B.M.答案共同努力，将其调整为正确的解决方案，这样效率更高，但一开始也遗漏了案例)
(还请注意，散列整数不会花费很多CPU时间，通常散列是是整数本身)
其余的看起来还可以.这是我的修改内容:
导入时间def GeneratingTable():A = {v表示i处于范围(1,10)中，j处于范围(0,10)中，k处于范围(0,10)中对于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]}打印(len(A))返回Adef ifPrime(n):我= 2当我*我< = n:如果n％i == 0:返回False我+ = 1返回Truedef check():返回sorted([如果ifPrime(p)，则为p在GeneratingTable()中为p的p]]开始= time.clock()x =检查()打印(len(x)，x)结束= time.clock()时间=结束-开始打印(时间) 结果:
3420203 [1247777777，1277777771，1277777773，1457777777，1487777777，1577777771，1577777777，1657777777，1777777741，1777777751，1777777777，1787777777，1877777773，1877777777，1877777779，1927777777，1957777777，2017777777，27777777777777772567777777，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、4777777777、4777777777、4777777777、4777777777、4777777777、4777777777、47777777774777777799、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，6777777777，6777777777，67777777776947777777，6977777771，6977777773，7037777777，7087777777，7327777777，7387777777，7487777777，7537777777，7547777777，7597777777，7607777777，7727777777，7777777019，7777777027，7777777057，7777777069，7777777081，7777103，77777777777777777237、7777777261、7777777327、7777777361、7777777369、7777777379、7777777391、7777777421、7777777429、7777777453、7777777493、7777777517、7777777549、7777777577、7777777597、7777777633、7777777639、7777777649、7777777777、77777737777777777789、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，97777777777777779477777773，9477777779，9547777777，9617777777，9677777771，9777777767，9777777787，9777777799，9817777777，9887777777，9937777777，9977777773]
注意:关于 isPrime 函数的效率:该函数可以有效地测试1个素数，但是当您要测试3000个以上的素数时，最好预先计算一个素数列表，直到 sqrt(10 ** 10)(例如使用筛子)并针对这些素数进行测试.计算素数列表是一项艰巨的工作，但是在测试许多素数时(如B.M答案中)很容易做到
so as it states in the title, I'm trying to generate a list of all the 10-digit prime numbers, that have 7x7 in a row. More precisely, I mean the numbers that can be written as follows: xxx7777777, xx7777777x, x7777777xx, 7777777xxx.
My idea is to generate a list of all this numbers, and then check which one of them is prime. The code is as follows:
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)
I am sure the number of primes I get this way is to high - it's 2115 and the number of elements in my list A is 3159. Is it a problem with my function "GeneratingTable" or checking whether the number is prime?
your prime function is wrong, it should increase i by 1, not 2, or you're missing some primes.
Then you should directly add to a set instead of creating a list when generating table, which saves memory & CPU time (also as Chris commented, you're performing loops starting at 0 or 1, which makes you miss values, I overlooked that in my previous post, now all indices start at 0). In that case, you can simplify even more using set comprehension, with a 5 formulas to be able to start indices at 1,0,0 and not forget the 7777770xx ones.
(this was tuned into the right solution with a collaborative effort with B.M. answer, which is more efficient, but also missed cases at first)
(also note that hashing integers doesn't cost much CPU time as usually the hash is the integer itself)
The rest seems okay. Here's my modifications:
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)
result:
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]
note: about the efficiency of the isPrime function: the function is efficient to test 1 prime, but when you have 3000+ primes to test, it's best to pre-compute a prime list up to sqrt(10**10) (for instance using a sieve) and test against those primes. Computing the list of primes is an effort, but well made up when testing a lot of primes (like in B.M answer)
这篇关于查找具有七个"7"的所有10位素数.连续-Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
