使用数组查找素数时p/ primes[i] >= primes[i]背后的逻辑

Question

所以我是一个C语言的初学者，虽然我有python的经验，但我不能把我的大脑围绕一个简单的问题。

如果我没记错的话，在Python中找到质数是一件容易的事情，但我在C中做同样的事情时遇到了困难。

因此，在我一直关注的教程中，这是使用数组查找3到100之间的质数的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main()
{
    int p;
    int i;

    int primes[50] = { 0 };
    int primeIndex = 2;

    bool isPrime;

    // hardcode prime numbers
    primes[0] = 2;
    primes[1] = 3;

    for (p = 5; p <= 100; p = p + 2)
    {
        isPrime = true;

        for (i = 1; isPrime && p / primes[i] >= primes[i]; ++i)
            if (p % primes[i] == 0)
                isPrime = false;

        if (isPrime == true)
        {
            primes[primeIndex] = p;
            ++primeIndex;
        }
    }

    for (i = 0;  i < primeIndex;  ++i)
         printf("%i  ", primes[i]);

    printf("\n");
    return 0;
}

上面代码中的第一个for循环是可以理解的，但第二个循环之后发生的事情让我感到困惑。

第二个for循环中的p / primes[i] >= primes[i]条件背后的逻辑是什么？

例如，如果我遵循循环，获取p = 5并应用条件，它将为5 / primes[1] >= primes[1]

因为我们知道primes[1] = 3，所以这将变成5 / 3 >= 3，它立即变成false。

请解释在第一个for循环之后发生了什么

编辑:我已经添加了python代码，我可以自己做。为什么在C中不能这样做：

lst = [2]
for i in range(3, 100):
     for j in range(2, i):
          if (i % j) == 0:
                break
     else:
          lst.append(i)

print(lst)

Answer 1

内部for循环尝试到包含sqrt(p)之前找到的所有奇素数，而不实际计算sqrt(p)。一旦找到除以p的质数，循环就会停止。它可能更具可读性，如下所示：

    isPrime = true;
    for (i = 1; p / primes[i] >= primes[i]; ++i) {
        if (p % primes[i] == 0) {
            isPrime = false;
            break;
        }
    }

在5的情况下，to循环不会开始，因为5 < 3*3，5是质数，7也是如此:不需要测试来确定它的素数。

得益于for语句的else:子句，您的python代码更加优雅，只有在循环正常退出时才会执行。然而，python版本中的算法效率要低得多，因为您测试了所有数字，包括偶数和直到i的所有除数。对于100来说，差异几乎不明显，但对于更大的范围，增加的复杂性将会显现出来。还要注意，为了使质数列表正确，应该将lst初始化为lst = [2]，并且可以删除冗余的if i > 1:。