对于判断一个数m是否为素数，最朴素的法是按素数的定义，试除以从2开始到m-1的整数，如果无一例外地不能整除，则该数定是素数，例如，实现的程序如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
using namespace std;
void paint(int a);
int main() {
cout<<"please input a number:";
int m;
cin>>m;
for(int i=2; i<m; i++) {
if(m%i == 0 ) {
cout<<m<<" isn't a prime.\n";
return 1;
}
}
cout<<m<<" is a prime.\n";
}
|
想一想，若2都不能除尽．还要试4，6，8…..吗？若3都不能除尽，还要试9，15，21…吗？等等。一个数，如果有因子的话那么在它的平方根数以内就应该有，否则就没有因子，例如，77的平方根值在8与9之间，因为77不是素数，则它一定有比8还小 的因子，它能被7整除，是理所当然的。
在数学上，假定某个整数m不是素数，则一定可以表示成两个因子的积：
m = i * j 假定 i <= j
则 i² ≤ m ≤ j²
即 i ≤ √m ≤ j
所以必定有—个因子不大于m的平方根，故判断m是否是素数，只要除到m的平方根就可以了，不必一直到m-1：因此，上面的程序可以修改为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <iostream>
#include <cmath>
using namespace std;
void paint(int a);
int main() {
cout<<"please input a number:";
int m;
cin>>m;
double sqrtm = sqrt(m * 1.0);
for(int i=2; i<sqrtm; i++) {
if(m%i == 0 ) {
cout<<m<<" isn't a prime.\n";
return 1;
}
}
cout<<m<<" is a prime.\n";
}
|
修改后的程序，效率提高了一些，例如，判断101是否为素数，本来要从2试除到100． 现在只要从2试除到10就行了。
事实上，中间的4，6，8也都无须试，大家可以想一想，在不明显增加程序复杂性 的基础上怎么修改程序，效率还会更高呢？
筛选法判断素数
从2开始的某个连续整数集合，留下2，除去所有2的倍数，留下3，除去所有3的倍数留下5再除去所有5的倍数，如此等等，留下某个最先遇到的素数，将其所有的倍数从该数集中去掉，最后，数集中就全是素数了，接下来要判断一个数是否为素数，可以该数为下标，访问素数集合，如果是则为素数，否则不是素数，例如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<iostream>
#include<vector>
#include<fstream>
using namespace std;
int main() {
vector<int> prime(10000,1);
for(int i=2; i<100; i++)
if(prime[i])
for(int j=i; j*i<10000; j++)
prime[i*j] = 0;
ifstream in("a.txt");
for(int a; in>>a && a>1 && a<10000; )
cout<<a<<" is "<<(prime[a] ? "":"not ")<<"a prime.\n";
}
|
在程序中，对于3来说，要去掉所有3的因子，包括6，12，18等，但事实上，偶数 在上一轮中已经作为2的倍数而去掉了，所以，这个过程还有一些重复操作，算法还有可以改进的地方。