Python 找出任意两个数之间的素数

Question

我试图在任意两个随机数之间找到质数。

首先，我写了这样的代码：

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, i):
        if i%j == 0:
            break
    else:
        print i,

现在对于测试用例，假设我输入 2、30 然后它会打印

2 3 5 7 11 13 17 19 23 29

现在分析，我们不需要在第二个循环中循环到 "i" 而是我们可以通过循环到 i/2 来做同样的事情，然后我将代码更改为：

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    for j in range(2, int(i/2)+1):
        if i%j == 0:
            break
    else:
        print i,

然后在第二个循环中循环到i/2，结果和上面一样。

现在，我正在尝试使用埃拉托色尼筛法打印素数，我使用的代码如下：

m,n = map(int, raw_input().split())
for i in range(m, n+1):
    sqrt_num = int(n**(0.5))
    for j in range(2, sqrt_num+1):
        if i%j == 0:
            break
    else:
        print i,

但它打印

7 11 13 17 19 23 29

对于相同的输入。

请帮助我理解我做错了什么。以及我如何使用这种方法完成相同的任务。

Answer 1

您的内部循环过去一直循环到 i-1 或 i/2。当 i 较小时，此内部循环较短，而当 i 变大时，此内部循环较长。

现在，您的内部循环上升到 sqrt_num，这是从 n 计算得出的常数。行为差异。

考虑i = 3，内循环从j = 2运行到j = 5，会发现i%j == 0的情况……具体来说，当j == 3.

明确一点：问题是“sqrt_num，它是一个常量”。将其更改为外部索引的平方根，i.

    sqrt_num = int(i**(0.5))

Python 找出任意两个数之间的素数

Python finding Prime Numbers between any two numbers

python

primes

sieve-of-eratosthenes