Python while 循环查找素数 [英] Python while loop for finding prime numbers

问题描述

作为 Python 的第一个练习，我尝试编写一个使用循环查找素数的程序.一切都适用于 for 循环，所以我尝试使用 while 循环.这有效，但程序返回了一些不正确的数字.

As a first exercise with Python, I'm trying to write a program using loops to find primes. Everything works with a for loop so I am trying to use a while loop. This works but the program returns a few incorrect numbers.

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 它返回:

So the weird thing is that for max_num=100 it returns:

[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，我不知道为什么.

which is correct except for 9, 25 and 49 and I can't figure out why.

推荐答案

您需要向上包括平方根.否则，您的算法将错过素数平方族(9、25 和 49 是素数平方).

You need to go up to and including the square root. Otherwise your algorithm will miss the family of prime squares (9, 25, and 49 are prime squares).

快速解决方法是将 < 替换为 <= 作为停止条件.

The quick fix is to replace < with <= as your stopping condition.

但考虑将停止条件改为

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

通过此测试，您不会进入和退出浮点数.

With this test, you don't dip in and out of floating point.

这篇关于Python while 循环查找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！