前两天在网上看到一种判断素数的方法（筛选法），跟平时老师讲的不太一样，于是亲手尝试了一下，果然，计算速度有很大差别！（前提是运算的数据很多，本文以1000000以内的素数为例！）
·普通方法
我们平时用的方法一般是拿到一个数（如17），然后从2开始去除17，若直到与17差1而余数仍不为零，则是素数。然后再细想其实没必要算到比17小1，而只要算到√17即可，因为17/√17=√17，再继续算的话，即使能除尽，结果也肯定是2~√17中的一个数，而这个数早已计算过。所以我们就可以限制除数从2~√17，当然在计算过程中，√17要取整。代码如下：
#include <iostream>
#include<fstream>
#include<ctime>
using namespace std;
#define MAX_NUM 1000000
int IsPrime[MAX_NUM + 10];
int main() {
int a = 0;
int i, j;
clock_t start_time,end_time;//计算程序运行时间
start_time = clock();
for (i = 2;i<=MAX_NUM;i++) {
IsPrime[i] = 1;//将1000000个数据在数组内的值赋成1
}
for (i = 2;i <= MAX_NUM;i++) {
for (j = 2;j <= (int)sqrt(i);j++) {
if (i%j == 0) {
IsPrime[i] = 0;
continue;
}
}
}
end_time = clock();
ofstream file;
file.open("sushu.txt");
file <<"素数输出："<< endl;
for (i = 2;i <= MAX_NUM;i++) {
if (IsPrime[i] == 1)
{
file << i << " ";a++;//输出数组内值为一对应的i值，即为素数，a用于记录素数个数
}
}
file << endl;
file << "----------------------------------" << endl;
file << "1000000以内的质数共有" << a << "个！" << endl;
file << "----------------------------------" << endl;
file.close();
cout << "此算法运行时间为：" << end_time - start_time << "ms" << endl;
cout << "结果已写入文件！" << endl;
return 0;
}
·筛选法
筛选法是指从2开始，依次找出其倍数并将其数组值置零，然后一直循环下去，直到将所有有因数的数据筛除。代码如下：
#include <iostream>
#include<fstream>
#include<ctime>
using namespace std;
#define MAX_NUM 1000000
int IsPrime[MAX_NUM + 10];
int main() {
int a = 0;
int i, j;
clock_t start_time,end_time;//计算程序运行时间
start_time = clock();
for (i = 2;i<=MAX_NUM;i++) {
IsPrime[i] = 1;//将1000000个数据在数组内的值赋成1
}
for (i = 2;i<=MAX_NUM;i++) {
if (IsPrime[i]==1) {
for (j = 2 * i;j <= MAX_NUM;j += i) {
IsPrime[j] = 0;//从2开始，依次找出其倍数并将数组值置零
}
}
}
end_time = clock();
ofstream file;
file.open("sushu.txt",ios::out||ios::app);
file <<"素数输出："<< endl;
for (i = 2;i <= MAX_NUM;i++) {
if (IsPrime[i] == 1)
{
file << i << " ";a++;//输出数组内值为一对应的i值，即为素数，a用于记录素数个数
}
}
file << endl;
file << "----------------------------------" << endl;
file << "1000000以内的质数共有" << a << "个！" << endl;
file << "----------------------------------" << endl;
file.close();
cout << "此算法运行时间为：" << end_time - start_time << "ms" << endl;
cout << "结果已写入文件！" << endl;
return 0;
}
运行结果：
