我怎样才能让我的代码在大值(最多1亿)时运行得更快？

Question

好的，背景知识:我正在解决一个问题，要求我找到一个数字'n‘，使得n-9，n-3，n+3，n+9是连续的素数，n-8，n-4，n+4，n+8是实数，然后我必须加上满足这个条件的前四个n。

问题是:代码的逻辑是否正确在这里无关紧要，因为我的代码在达到1亿之前就崩溃了。我甚至不能检查代码的输出，它在100万的情况下工作得很好，但是对于更大的数字，它的伸缩性不好。

我做了什么:我使用了erath的筛子。为了得到最多1亿的素数，我们称之为M。由于实数可以被6或4整除，我创建了另一个集合来存储这些数字，然后从那个列表中创建了一个包含满足条件的数字的集合：“N -8，n-4，n+4，n+8是实数”，我们称之为N。最后，我迭代N中的每个元素a，检查a- 9，a- 3，a+ 3，a+9是否是素数集合的一部分。

如果任何人有任何关于如何加快速度或任何更好的算法的提示，我将不胜感激

代码

def SieveOfEratosthenes(n):
    m = set()
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False
    for p in range(n + 1):
        if prime[p]:
            m.add(p)
    return m

#creates set that stores multiples of 4 and 6

def ps1(n):
    s = set()
    for i in range(1, n+1):
        if i%4 == 0 and i%6 == 0:
            s.add(i)
    return s

#checks whether any number satisfies n -8, n-4, n+4, n+8 must be practical and stores it in a set

def ps2(l):
    q = set()
    for i in l:
        if ((i-8) in l) and ((i-4) in l) and ((i+4) in l) and ((i+8) in l):
            q.add(i)
    return q

#using the numbers stored in the prev set, i check the last condition n-9, n-3, n+3, n+9 must be in the 
prime list
def TotalSieve(k, l):
    q = set()
    inc = 0
    for i in k:
        if inc != 4:
            if ((i-9) in l) and ((i-3) in l) and ((i+3) in l) and ((i+9) in l):
                inc = inc + 1
                q.add(i)
        else:
            print("Found 4")
    return q
                                                                       
# driver program
if __name__=='__main__':
    n = 1000000000
    m = SieveOfEratosthenes(n)
    p = ps1(n)
    p = ps2(p)
    f = TotalSieve(p, m)
    elem1 = f.pop()
    elem2 = f.pop()
    elem3 = f.pop()
    elem4 = f.pop()
#add the first four numbers that satisfy the conditions
    tot = elem1 + elem2 + elem3 + elem4
    print(tot)

Answer 1

首先，ps1错了。测试应该是or，而不是and。

接下来，如果n可以被4整除，那么所有的n-8, n-4, n+4, n+8也都可以被4整除。如果n不能被4整除，那么它们中的任何一个都不能被4整除，其中一些也不能被4整除。这意味着您只对n是4的倍数感兴趣。

最后，我知道这个问题意味着一些严肃的数论作业。暴力是行不通的。