我的算法思想和實現方式都在代碼和注釋當中呢，這樣的方式確實使算法復雜度降低一個等級，很好啊。 ~~~ #include <stdio.h> #include <time.h> /** * 利用數組求前n個質數 * 確定一個數m是否為質數，可以用已求出的質數對m * 的整除性來確定 */ //如果不知道質數的特性和想不到優化思路的方法 void getNPrimes_normal(); //優化之后的方法 void getNPrimes_optimize(); int main(void) { clock_t start,end; start = clock(); //開始時，取得開始時間。 //通常的做法的運行時間，輸入的n=10000 //getNPrimes_normal(); //優化后的運行時間 getNPrimes_optimize(); end = clock(); //結束時，取得結束時間 printf("Run time: %lf S",(double)(end-start)/CLOCKS_PER_SEC); return 0; } //通常用到的想法 void getNPrimes_normal(){ /** * 用于保存質數的數量 * @brief count */ int count; printf("Please the count of prime number:\n"); scanf("%d",&count); //使用數組來保存所求出的質數 int primes[count]; /** * 首先，第一個已知的質數是2， * 則計算應該從3開始 */ primes[0] = 2; int pc = 1; int m = 3; //從數字3開始 while(pc < count){ int k = 0; // 這里只要找不到質數，就會一直在這個循環中 while(k < pc){ if(m % primes[k] == 0){ m += 1; k = 0; }else{ k++; } } //找到質數之后，跳出上面的循環 //這個的執行是先執行primes[pc] = m; //再去執行pc++; primes[pc++] = m; m+=1; } /** * 對質數進行輸出操作 * */ for(pc = 0;pc < count;pc++){ printf("%4d\t",primes[pc]); } } //優化之后的方法 void getNPrimes_optimize(){ /** * 用于保存質數的數量 * @brief count */ int count; printf("Please the count of prime number:\n"); scanf("%d",&count); //使用數組來保存所求出的質數 int primes[count]; /** * 首先，第一個已知的質數是2， * 則計算應該從3開始 */ primes[0] = 2; int pc = 1; int m =3; //從數字3開始 while(pc < count){ /** * 首先需要解決的是如何判斷一個數是一個質數 * 1：除了數字2之外，其他所有的質數都是奇數 * 2：假設某一個數字是k，只要判斷k能否被k之前 * 的質數整除就可以了，如果能夠整除，則k就是 * 合數，如果不能整除，k就是質數 * * 但是，為了減少算法的復雜度，我們這樣設想 * p*q=k * 則肯定p和q中： * p*p <=k的話，q*q >= k * 則，只要求k能否被k的平方根之前的數字整除就可以了。 * * 基于這個思想，我們的實現方式如下： */ int k = 0; // 這里只要找不到質數，就會一直在這個循環中 while(primes[k] * primes[k] <= m){ if(m % primes[k] == 0){ m += 2; //除了數字2之外，其他所有的質數都是奇數 k = 1; //不用使用數字2去測試 }else{ k++; } } //找到質數之后，跳出上面的循環 //這個的執行是先執行primes[pc] = m; //再去執行pc++; primes[pc++] = m; m+=2; } /** * 對質數進行輸出操作 * */ for(pc = 0;pc < count;pc++){ printf("%4d\t",primes[pc]); } } ~~~ 下面是我的運行結果，第一個是沒有優化的結果，第二個是經過算法優化后的結果，效果還是很明顯的。 這個是沒有優化的結果：  這個是優化之后的結果：