這是列印素數的代碼。
#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回圈中的條件是如何作業的，isPrime變數的用途是什么？
uj5u.com熱心網友回復：
該代碼正確計算并列印所有小于或等于 100 的素數。
為什么需要硬編碼 2 個素數（2 和 3）？
2是一個特例：它是唯一的偶素數。2被硬編碼為第一個素數，所以外回圈只測驗奇數。
3是硬編碼的，因此外回圈可以依靠陣列內容來確定其停止條件p / primes[i] >= primes[i]。陣列中至少需要有一個奇素數，以避免對陣列索引進行額外的測驗，例如i < primeIndex.
正如chux評論的那樣，內回圈可以從索引開始，i = 0然后只2需要硬編碼到陣列中。篩選程序的效率會稍低一些，因為所有數字都將不必要地被測驗為可被 2 整除的，因為所有測驗的數字都是奇數，因此可以跳過這一步。
第一個
for回圈中布爾運算式的用途是什么？
第一個for回圈中的條件測驗是p <= 100。該程式列舉小于或等于 的素數100。該primes陣列的長度50足以滿足此范圍。如果范圍更大，則需要擴展陣列大小。
布爾變數isPrime用于存盤素性測驗的結果。當且僅當在內回圈中找到素數除數時，它被初始化為true并且將被重置為false。
在內回圈之后測驗變數以檢查是否p應附加到素數串列。
第二個for回圈中的條件isPrime && p / primes[i] >= primes[i]是一個優化：它允許回圈在找到除數后立即停止。該測驗可以簡化為p / primes[i] >= primes[i]，回圈將繼續測驗直到 的平方根的素數除數p。在break找到除數時添加陳述句是一種提前停止回圈以提高效率的替代方法。
有人可以解釋一下內部 for 回圈是如何作業的嗎？
內部回圈對質數除數進行迭代，直到發現一個余數為 0 ( p % primes[i] == 0) 或直到除數大于p( p / primes[i] >= primes[i]) 的平方根。
請注意，primes不需要初始化陣列。
這是一個簡化版本：
#include <stdio.h>
#include <stdbool.h>
int main() {
int primes[50];
int i, p, primeIndex;
// hardcode 2 prime numbers
primes[0] = 2;
primes[1] = 3;
primeIndex = 2;
// enumerate odd numbers from 5 to 100
for (p = 5; p <= 100; p = p 2) {
// use a boolean variable that will be set to false if p is composite
bool isPrime = true;
// test all odd prime divisors up to the square root of p
for (i = 1; p / primes[i] >= primes[i]; i) {
if (p % primes[i] == 0) {
isPrime = false;
break;
}
}
// if p is prime, add it to the array.
if (isPrime) {
primes[primeIndex ] = p;
}
}
for (i = 0; i < primeIndex; i)
printf("%i ", primes[i]);
printf("\n");
return 0;
}
這是一個使用函式的更簡單的版本：
#include <stdio.h>
#include <stdbool.h>
// test if an odd number greater than 3 is a prime
bool isOddPrime(int p, const int *primes) {
for (int i = 1; p / primes[i] >= primes[i]; i) {
if (p % primes[i] == 0)
return false;
}
return true;
}
int main() {
int primes[50] = { 2, 3 }; // hardcode 2 prime numbers
int primeIndex = 2;
for (int p = 5; p <= 100; p = p 2) {
if (isOddPrime(p))
primes[primeIndex ] = p;
}
for (i = 0; i < primeIndex; i)
printf("%i ", primes[i]);
printf("\n");
return 0;
}
uj5u.com熱心網友回復：
對邊緣情況進行硬編碼并不少見，尤其是在邊緣情況不多的情況下。然而，其余的代碼并不好——我已經嘗試過，但結果并不好。
在這里，您可以調查并嘗試進一步優化。O(n**2)。
int main()
{
int n, i, fact, j;
printf("Enter the upper limit: ");
scanf("%d", &n);
printf("Prime numbers up to the %d are: \n", n);
for( i = 1; i <= n; i )
{
fact = 0;
for ( j = 1; j <= n; j )
{
if( i % j == 0 )
fact ;
}
if ( fact == 2 )
printf("%d ", i);
}
return 0;
}
例如，內回圈測驗用例可以從 縮小j <= n到j <= n/2。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/393273.html