C++求n以内的所有素数(n>=2)的三种方法

这里将test.txt文件写为500000，意为求500000以内的所有素数并将其打印。(可以在2~2147483647内任意改变此值)

第一种常规求法：

#include<iostream>
using namespace std;
int main()
{
	freopen("d:\\HHHtemp\\test.txt","r",stdin);//以下所有输入均从test.txt中打开
	int n;
	cin>>n;
	for(int i = 2; i < n; ++i)
	{		
		int k;
		for(k = 2; k < n; ++k)
		if(i%k == 0)break;//如果找到一个因子k能将i除尽则跳出
		if(k == i)//表明没有找到任何一个符合要求的因子k，所以为素数
		cout<<i<<" ";
	}	
	return 0;
}

耗时为一分钟。

第二种改进方法：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	freopen("d:\\HHHtemp\\test.txt","r",stdin);
	int n;
	cin>>n;
	cout<<2<<" ";
	for(int i = 3; i < n; i+=2)
	{
		int k;
		for(k = 3; k*k < n; k+=2)//只需在k<√n范围找到一个k即可，也可以用sqrt，需加头文件cmath			
			if(i%k == 0)break;
		if(k*k > n)//表明没有从没有找到符合的k
		cout<<i<<" ";
	}
	return 0;
}

第二种方法耗时为15.43s

第三种，筛法求素数

#include<iostream>
using namespace std;
#define MAX 500000
char isPrime[MAX+10];//用char类型节省内存，int占4字节，char占1字节，效果都一样，因为这里用1，0代表素数与否
int main()
{
	for(int i = 2; i <= MAX; ++i)//先将所有元素都认为是素数 
		isPrime[i]=1;
	for(int i = 2; i <= MAX; ++i)
	{
		if(isPrime[i])//只用标记素数的倍数
			for(int j = i * 2; j <= MAX; j += i)
				isPrime[j] = 0;	//将其标记为非素数
	}
	for(int i = 2; i <= MAX; ++i)//依次输出素数
		if(isPrime[i])
			cout<<i<<" ";
	return 0;
}

耗时为14.48s。

看似2，3种方法用时差不多，实际上如果规模再大一些筛法求素数效率比第二种高得多，因为筛法求素数使用的内存空间更多，这里用内存换取了时间。
思路：内存空间和时间可以通过算法相互换取和转换。