用于查找素数的Python while循环

Question

作为Python的第一个练习,我正在尝试使用循环编写程序来查找素数.一切都与for循环一起工作所以我试图使用while循环.这有效,但程序返回一些不正确的数字.

import math
# looking for all primes below this number
max_num = int(input("max number?: "))

primes = [2]  # start with 2
test_num = 3  # which means testing starts with 3

while test_num < max_num:
    i = 0
    # It's only necessary to check with the primes smaller than the square
    # root of the test_num
    while primes[i] < math.sqrt(test_num):
        # using modulo to figure out if test_num is prime or not
        if (test_num % primes[i]) == 0:
            test_num += 1
            break
        else:
            i += 1
    else:
        primes.append(test_num)
        test_num += 1

print(primes)

所以奇怪的是max_num=100它返回:

[2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

这是正确的,除了9,25和49,我无法弄清楚为什么.

Answer 1

你需要去包括平方根.否则,您的算法将错过素数平方族(9,25和49是素数正方形).

快速的解决办法是更换<与<=作为停止条件.

但考虑改变停止条件

primes[i] * primes[i] <= test_num

通过此测试,您不会进出浮点.