尝试使用 Python 查找质数

Question

下面是我使用 Python 查找素数的代码，但它不起作用。这里函数 prime 将接受一个整数作为输入，而 return 无论它是否是素数。能否请您解决问题并解释一下。

def prime(x):
    if x == 0 or 1:
        return False
    elif x == 2:
        return True
    else:
        for n in range(2, x):
            if x % n == 0:
                return False
            else:
                return True

我想我已经解决了第一个问题，第一个"if"语句应该是if x == 0 or x == 1。现在剩下的呢。

Answer 1

问题是 return true 在 for 循环完成之前不应该发生。

我们在原始代码中的内容是一些简单情况的测试（x 小于 3）然后是测试所有较大数字的循环。

在循环中，尝试将 x 除以一个较小的数字（从 2 开始），然后如果除以均等则返回 False，否则返回 True，这是错误的，而不是返回 true，应该允许循环重复，并且应该用下一个数字再次尝试除法，并且只有在除数供应（来自 for 循环）已经耗尽之后才应该返回 true。

这是一个固定版本：

def prime(x):
    if x <= 1:
        return False
    elif x == 2:
        return True
    else:
        for n in range(2, x):
            if x % n == 0:
                return False

        return True

其他人评论说循环不需要一直持续到 x 并且在 sqrt(x) 停止就足够了，他们是正确的。这样做几乎在所有情况下都会使其更快。

如果你有一个小素数列表（最大为 sqrt(x)），可以得到另一个加速 - 你只需要测试 sqrt(x) 以下素数的整除性，而不是该范围内的每个整数。

Answer 2

你的 for 循环是什么？

if x % n == 0:
    return False
else:
    return True

^{顺便说一下等于 return bool(x % n)}

因此，您 return 在第一次迭代中 n == 2。

whole for 循环等于 return bool(x % 2)，它只是检查 x 是否可以被 2 整除。
这不是你想要的。

那么，你想要什么？

您想检查 x 是否不能被 range(2, x) 中的任何数字整除。

你知道x是不是素数，如果你从[=19中找到一个 n =]，其中 x % n == 0 是 True。
你知道x是素数，当range(2, x)中没有n时，x % n == 0就是True .

你什么时候可以说范围中n的none是x的约数？
检查范围内的所有 n 之后！

After是这里的关键
在循环之后，你试图找到除数，你只能告诉x是素数。

我希望你现在能理解其他人在没有解释的情况下发布的代码。

注意：替代语法

其他人发布的代码是正确的。但是，在 Python 中有第二种写 for 的方法，使用 for .. else:

for x in range(2, x): if x % n == 0: return False else: return True

Answer 3

下面的代码用于查找从 2 到第 n 个数的质数。例如，下面的代码将打印 2 到 50 之间的素数，并且还将打印 2 到 5o 之间的非素数。

import time
i=2
j=2
count=0
while(i<50):
 while (i>j):
    if (i%j)==0:
      count=count+1
      j=j+1
    else:
      j=j+1
 if count==0:
    print i," is a prime"
 else:
    print i," is not a prime"
 i=i+1
 j=2
 count=0
 time.sleep(2)

尝试使用 Python 查找质数

Trying to find the prime numbers using Python

python

那么，你想要什么？

注意：替代语法