Python - 为什么这个质数检查算法不起作用？

Question

我有我写了这个Python代码：

from math import * 

limit = 100000 
primes = [2] 

for i in range(3, limit+1, 2): 
    is_prime = True 
    for j in range(3, floor(sqrt(i)), 2): 
     if i % j == 0: 
      is_prime = False 
      break 
    if is_prime: primes.append(i) 

print(len(primes)) 

它说，有9676素数小于100 000，当它应该是9592.这给出了正确的答案，如果我只用i取代floor(sqrt(i))，但那么它非常缓慢。为什么我的算法不工作？

Answer 1

举个例子来说i == 9。以下范围：

for j in range(3, floor(sqrt(i)), 2): 

则计算结果为：

for j in range(3, 3, 2): 

...这是一个空的列表，防止非黄金9被排除。您需要更高一点以确保考虑方块的根：

for j in range(3, floor(sqrt(i)) + 1, 2): 

Answer 2

你包括其他的素数的平方素数 - 我改变了开方范围定义在你的代码来获得：

from math import * 

limit = 100000 

primes = [2] 

for i in range(3, limit+1, 2): 
    is_prime = True 
    for j in range(3, floor(sqrt(i))+1, 2): 
     if i % j == 0: 
      is_prime = False 
      break 
    if is_prime: primes.append(i) 

print(len(primes)) 

导致9592个素数发现