运用C++查找素数-Toy模板网

这篇具有很好参考价值的文章主要介绍了运用C++查找素数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

查找素数是在学习C/C++中基本的问题，主要是考察对循环的应用，逻辑上并不是很难。

对于常规的素数查找法，解题步骤通常是：（以查找100以内的素数为例）

1.从2开始逐步循环；

2.再进行嵌套循环，判断2能否被2之后的数字整除；

3.如果恰好有能被整除的则结束循环；如果没有则输出素数；

4.一直重复上面的步骤，就能找出100以内的全部素数。

代码如下

#include<iostream>
using namespace std;
int main()
{
	int i,j,k,MAX;
	cout<<"请输入你要查找多少以内的素数?"<<endl;
	cin>>MAX;
	for(i=2;i<=MAX;i++)
	{
		for(j=2;j<i;j++)
			if(i%j==0)
				break;
		if(j==i)
		{
			cout<<i<<"  ";
		}
	}
	cout<<endl;
	return 0; 
}

运行结果为：

运用C++查找素数

这个代码足够解决这个问题，但是缺陷就是速度太慢，时间复杂度达到!!!

仅仅是求100以内的素数就花了2ms；求100000以内的素数花了2218ms！

所以我们进一步改善求解的思路。

我们知道如果一个数不被它以内的素数整除，就代表它是素数！有了这个思想，我们设计出了进阶算法，来求素数。

代码如下：

#include<iostream>
using namespace std;
int main()
{
	// 定义一个数组存放素数 
	int MAX,n=1,j;
	cout<<"请输入你要查找多少以内的素数?"<<endl;
	cin>>MAX;
	int list[MAX];
	// 查找MAX以内的素数存放到数组中
	list[0]=2; 
	for(int k=3;k<=MAX;k++)
	{
		for(j=0;j<n;j++)
		{
			if(k%list[j]==0)
				break;
		}
		if(j==n)
		{
			list[n]=k;
			n++;
		}
		
	}
	for(int i=0;i<n;i++)
		cout<<list[i]<<"  ";
	cout<<endl;
	cout<<"在"<<MAX<<"以内一共有"<<n<<"个素数！"<<endl; 
	return 0;
}

运行结果为：

运用C++查找素数

改良后的代码所花时间更好，在求100以内的素数时花费0ms，在求10000以内的素数时仅花费2ms！下面我们进行一下比较。

在两个代码上都加上可以求运算时间的函数，代码如下：

// 常规求法
#include<iostream>
#include<ctime> 
using namespace std;
int main()
{
	// 计算运行的时间
	int begintime,endtime;
	int i,j,k,MAX;
	cout<<"请输入你要查找多少以内的素数?"<<endl;
	cin>>MAX;
	int n=0;
	begintime=clock();	//计时开始
	for(i=2;i<=MAX;i++)
	{
		for(j=2;j<i;j++)
			if(i%j==0)
				break;
		if(j==i)
		{
			cout<<i<<"  ";
			n++; 
		}
	}
	endtime = clock();	//计时结束
	cout<<endl;
	cout<<"在"<<MAX<<"以内一共有"<<n<<"个素数！"<<endl;
	cout<<"花费时间为："<<endtime-begintime<<"ms"<<endl;
	return 0; 
}

// 改善算法代码
#include<iostream>
#include<ctime> 
using namespace std;
int main()
{
	// 计算运行的时间
	int begintime,endtime; 
	// 定义一个数组存放素数 
	int MAX,n=1,j;
	cout<<"请输入你要查找多少以内的素数?"<<endl;
	cin>>MAX;
	int list[MAX];
	// 查找MAX以内的素数存放到数组中
	list[0]=2; 
	begintime=clock();	//计时开始
	for(int k=3;k<=MAX;k++)
	{
		for(j=0;j<n;j++)
		{
			if(k%list[j]==0)
				break;
		}
		if(j==n)
		{
			list[n]=k;
			n++;
		}
		
	}
	endtime = clock();	//计时结束
	for(int i=0;i<n;i++)
		cout<<list[i]<<"  ";
	cout<<endl;
	cout<<"在"<<MAX<<"以内一共有"<<n<<"个素数！"<<endl; 
	cout<<"花费时间为："<<endtime-begintime<<"ms"<<endl;
	return 0;
}

分别求100000以内的素数，我们可以得到结果分别为：

运用C++查找素数