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个素数小于10万,当它应该是9592.如果我floor(sqrt(i))用公正替换它给出正确的答案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):