Python 素数生成器输出 4

Question

我有一个学校练习，我必须制作一个素数生成器并稍后对其进行优化。在我做了一些优化之后，我的生成器也开始打印数字“4”，这显然不是质数。

我的代码如下所示：

import time
#Primzahlen errechnen
c = 0
print("Enter Upper Value:")
Max_wert = input()
x = int(Max_wert)

print("Prime Numbers between 0 and ", x, "are:")
time.sleep(1) # Pause für 2 Sekunden

for num in range(2, x):
    num2 = int(num / 2)
    for i in range(2, num2):
        if (num % i) <= 0:
            break
    else:   
        print(num)
        c+=1

print(c, "Prime Numbers were found")

当我删除行：> num2 = int(num / 2) 并将 for 循环中的 num2 更改回 num 时，一切正常。

Answer 1

问题是在for循环中你必须测试从2到floor(sqrt(num))而不是num/2（任何进一步的控制都是无用的，检查一下：Why do we check up to the square root of a prime number to determine if it is prime?) 和，最重要的是，i的范围必须在range(2, num2 + 1)而不是range(2, num2)

之间

for 循环代码将是：

for num in range(2, x):
    num2 = math.floor(math.sqrt(num))
    for i in range(2, num2 + 1):
        if (num % i) <= 0:
            break
    else:   
        print(num)
        c+=1

示例输出为：

Enter Upper Value:
10
Prime Numbers between 0 and  10 are:
2
3
5
7
4 Prime Numbers were found

Answer 2

循环中for i in range(2, num2):当num在2到5之间时程序流不会进入for循环

所以它们 2、3、4、5 只是被打印出来，而不是因为它们是质数还是非质数。

因为num2=int(num/2)，当num在[2,5]时，for循环范围为(2,1)(2,1)(2,2)(2,2 ).

当数字=2,3 range(2,1) 没有意义，因为您要求它从 2 开始一直到 1，因此它退出循环并直接进入 else 块打印 2 和 3。

当数字=4,5 range(2,2) 不会给出任何东西，因为你要求它从 2 开始一直到 2（不包括在内）所以它再次直接进入其他块打印 4 和 5.

对于 num 的值，超过 5 个你的代码可以正常运行。

所以你的 for 循环应该是：

for num in range(2, x):
    num2 = int(num / 2 + 1)
    for i in range(2, num2):
        if (num % i) <= 0:
            break
    else:   
        print(num)
        c+=1

Python 素数生成器输出 4

Python Prime Number Generator Prints 4

python

primes

for-loop

generator