素数判定算法的实现
1. 素数判定问题
素数判定问题是一个非常常见的问题，本文介绍了常用的几种判定方法。
2. 原始算法
素数的定义是，除了能被1和它本身整除而不能被其他任何数整除的数。根据素数定义 只需要用2到n-1去除n，如果都除不尽，则n是素数，否则，只要其中有一个数能整除则n不是素数。
bool is_primer1(int num) {
int i;
for(i = 2; i < num; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
3. 改进算法
n不是素数，则n可表示为a*b，其中2<=a<=b<=n-1,则a，b中必有一个数满足：1<x<=sqrt(n)，因而，只需要用2~sqrt(n)去除n，这样就得到一个复杂度为O(sqrt(n))的算法
bool is_primer2(int num) {
int i;
int upper = sqrt(num);
printf("primer2:%d\n", upper);
for(i = 2; i <= upper; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
4. 筛选算法
更高效地素数判断方法应该是将素数预先保存到一个素数表中，当判断一个数是否为素数时，直接查表即可。这种方法需要解决两个问题：
(1) 怎样快速得到素数表？（采用筛选方法）
(2) 怎样减少素数表的大小？（采用位图数据结构）
对于1到n全部整数，逐个判断它们是否是素数，找出一个非素数，就把它挖掉，最后剩下的就是素数。具体方法是：
<1> 定义is_primer[i] = true;
<2> 从2开始，依次遍历整个is_primer(直到sqrt(N))，如果is_primer[i]=true,则is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10，则
从2开始遍历：
is_primer[2]=true，则is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true
is_primer[3]=true，则is_primer[6]= is_primer[9]= true
为了减少内存使用率，算法使用了位图数据结构，关于位图，可参考：http://www.jb51.net/article/54439.htm
bool load_primer_table1() { //保存素数表
int i;
for(i = 1; i < INT_MAX; i++) {
if(i % 2 != 0 //偶数一定不是素数
&& is_primer2(i)) {
set(i);
}
}
}
bool load_primer_table2() {//另一种更快的方法保存素数表
int i, j;
for(i = 1; i <= INT_MAX; i++) {
if( i % 2) {
set(i);
} else {
clear(i);
}
}
int upper = sqrt(INT_MAX);
for(i = 1; i <= upper; i++) {
if(test(i)) {
for(j = i + i; j < INT_MAX; j += i)
set(i);
}
}
}
bool is_primer3(long num) { //查表判断是否为素数
if(test(num))
return true;
return false;
}
5. 优化的筛选算法
(1) 存储方式优化
- 上一篇：关于背包问题的一些理解和应用
- 下一篇：数据结构之红黑树详解
