因此，從我一直遵循的教程中，這是使用陣列查找 3 到 100 之間的素數的代碼。第二個 for 回圈中 p / primes[i] >= primes[i] 條件背后的邏輯是什么？
例如，如果我按照回圈取 p = 5 并應用條件，它將是 5 / primes[1] >= primes[1]：
因為我們知道 primes[1] = 3 這將變成 5 / 3 >= 3 立即變為假。應該進行測驗以確保 p 的值不超過素數 [i] 的平方根，但這里 p / 素數 [i] >= 素數[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;
}
uj5u.com熱心網友回復：
邏輯是這樣的：
- 在每對因子 (m_1, m_2) 中，m_1 <= m_2 或 m_2 <= m_1
- 如果一個數 n 有一個乘法因子 m_1，它也有一個因子 m_2 = n / m_1。所以因子實際上是成對的：m 和 n/m。
- 由于 (1. 2.)，如果 m 是一個因子 n，使得 m > n/m，那么 n/m 也必須是 n 的一個因子，使得 (n/m) <= n/(n/m )。
因此，搜索“小”因素就足夠了，以驗證沒有更大的因素。
uj5u.com熱心網友回復：
... 應該進行測驗以確保 的值
p不超過primes[i]... 的平方根
不，它是周圍的其他方法：“測驗，以確保價值primes[i]不超過的平方根p”
或者：“測驗以確保primes[i]平方的值不超過p”。
只迭代到√p
為了只迭代到 的根p，而不是p / primes[i] >= primes[i]，代碼可以考慮類似的：
p >= sqrt(primes[i])
// or
p >= primes[i] * primes[i]
sqrt(primes[i])引入浮點數學。sqrt()沒有具體說明，只是close。與整數數學相比，FP 數學也很昂貴。使用 時long long，會出現更多的舍入問題。primes[i] * primes[i]當is near時有溢位和未定義行為的風險。pINT_MAXp / primes[i] >= primes[i]（或最好是primes[i] <= p / primes[i]）都沒有問題。它的計算成本可能很少，因為一個好的編譯器會看到下一個p % primes[i]并以大約一個的成本執行兩種計算。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/341603.html
上一篇：長C整數的Fortran互操作性