p / 素数[i] >= 素数[i] 背后的逻辑

Question

所以从教程中，我一直在遵循这段代码，使用数组找到3到100之间的素数。第二个for循环中的p/primes[i]>= primes[i]条件背后的逻辑是什么?

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

因为我们知道质数[1]= 3，这将变成5/3>= 3，这立即变成假的。应该有一个测试来确保p的值不超过质数的平方根[i]但这里p/primes[i]>= primes[i]有质数[i]的平方根

enter code here

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;

}

Answer 1

逻辑是:

1. 在每一对因子(m_1, m_2)中，m_1 <= m_2或m_2 <= m_1
2. 如果一个数字n有一个因数m_1，那么它也有一个因数m_2 = n/m_1。因此，因子实际上是成对的:m与n/m。
3. 由于(1.+2.)，如果m是因子n，使得m>n/m，则n/m也必须是n的一个因子，使得(n/m) <= n/(n/m)。

所以搜索"small"因子，以验证是否有较大的。

Answer 2

…应该有一个测试，以确保p的值不超过primes[i]的平方根…

。

"确保primes[i]值不超过p的平方根">

或:"test以确保primes[i]的平方值不超过p"

---

只迭代到√p

如果只迭代到p的根，而不是p / primes[i] >= primes[i]，代码可以考虑类似的:

p >= sqrt(primes[i])
// or 
p >= primes[i] * primes[i]

• sqrt(primes[i])引入浮点数学。sqrt()不是指定的，只是接近。与整数数学相比，FP数学也很昂贵。当使用long long时，会出现更多舍入问题。

• primes[i] * primes[i]风险溢出和未定义行为当p靠近INT_MAX时。

• p / primes[i] >= primes[i](或者最好是primes[i] <= p / primes[i])都没有问题。它的计算成本可能很低，因为一个好的编译器会看到下一个p % primes[i]，并以大约一次的成本执行两次计算。