利用数组求前n个质数
我的算法思想和实现方式都在代码和注释当中呢,这样的方式确实使算法复杂度降低一个等级,很好啊。
#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]);
}
}
下面是我的运行结果,第一个是没有优化的结果,第二个是经过算法优化后的结果,效果还是很明显的。
这个是没有优化的结果:
这个是优化之后的结果:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。