python - 查找连续七个 "7"的所有 10 位素数 - Python

Question

正如标题中所述，我正在尝试生成所有 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”有问题还是检查数字是否为素数？

Answer 1

你的 prime 函数是错误的，它应该将 i 增加 1，而不是 2，或者你遗漏了一些素数。

然后你应该直接添加到一个set而不是在生成表时创建一个列表，这样可以节省内存和 CPU 时间(也正如 Chris 评论的那样，你正在执行从 0 或 1 开始的循环，这让你错过了值(value)，我在我之前的帖子中忽略了这一点，现在所有索引都从 0 开始)。在这种情况下，您可以使用 set comprehension 进行更多简化，使用 5 个公式可以从 1,0,0 开始索引，并且不要忘记 7777770xx。

(这是通过与 B.M.answer 的协作努力调整为正确的解决方案，效率更高，但一开始也会遗漏案例)

(另请注意，散列整数不会占用太多 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 答案)很好地弥补了