如何使我的代码在大值(高达一亿)下运行得更快

Question

好的，背景：我正在解决一个问题，这个问题要求我找到一个数字"n"，使n-9，n-3，n+3，n+9是连续素数，n-8，n-4，n+4，n+8是实际数字，然后我必须将满足这个条件的前四个n相加。

问题是：代码的逻辑是正确的还是不正确的在这里无关紧要，因为我的代码在达到1亿之前就崩溃了。我甚至无法检查代码的输出，它适用于100万，但不能很好地扩展到更大的数字。

我做了什么：我用了埃拉斯的筛子。。。为了得到高达一亿的素数，我们称之为M。由于实际数字可以被6或4整除，我创建了另一个集合来存储这些数字，然后从这个列表中创建了一个集合，其中包含满足这个条件的数字："n-8，n-4，n+4，n+8是实际数字"，我们称其为n。最后，我迭代n中的每个元素a，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的倍数感兴趣。

最后，我知道这个问题意味着一些严肃的数论作业。残酷的武力是做不到的。