利用数组求前n个质数
最后更新于：2022-04-01 14:28:26
我的算法思想和实现方式都在代码和注释当中呢，这样的方式确实使算法复杂度降低一个等级，很好啊。
~~~
#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]);
}
}
~~~
下面是我的运行结果，第一个是没有优化的结果，第二个是经过算法优化后的结果，效果还是很明显的。
这个是没有优化的结果：
这个是优化之后的结果：
