如何检查大素数之间的条件

Question

小于201920190的质数如何找到那些在其str表示中没有数字'7'的质数?我需要计算不包含'7'的质数的个数(count)。

标准筛的实现太慢了，它只会卡住计算。

def SieveOfEratosthenes(num):
prime = [True for i in range(num+1)]
# boolean array
p = 2
while (p * p <= num):

# If prime[p] is not
# changed, then it is a prime
if (prime[p] == True):

# Updating all multiples of p
for i in range(p * p, num+1, p):
prime[i] = False
p += 1

# Print all prime numbers
for p in range(2, num+1):
if prime[p]:
#here added additional check to only print those that have no digit 7
if '7' not in str(p):
print(p)


# Driver code
if __name__ == '__main__':
num = 201920190
print("Following are the prime numbers smaller"),
print("than or equal to", num)
SieveOfEratosthenes(num)

如何做得更好?

Answer 1

也许是作弊，但如果你的优先级只是得到一个数字，你可以下载一个到201920190的所有质数的列表，例如从https://primes.utm.edu/lists/small/millions/(大约有1200万个)，然后通过该列表计数。

这并不像让你自己的筛代码工作那样令人满意，但它非常有效!