我的算法思想和实现方式都在代码和注释当中呢，这样的方式确实使算法复杂度降低一个等级，很好啊。 ~~~ #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]); } } ~~~ 下面是我的运行结果，第一个是没有优化的结果，第二个是经过算法优化后的结果，效果还是很明显的。 这个是没有优化的结果：  这个是优化之后的结果：