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. 挑选优化算法
更高效率地素数判断方式应该是将素数事先储存到一个素数表中，当分辨一个数是不是为素数时，立即查询表就可以。这类方式必须处理2个难题：
(1) 怎样快速获得素数表？（选用挑选方式）
(2) 如何降低素数表的尺寸？（选用位图文件算法设计）
针对1到n所有整数金额，逐一分辨他们是不是素数，找到一个非素数，就把它挖去，最终剩余的便是素数。具体做法是：
<1> 界定is_primer[i] = true;
<2> 从4开始，先后解析xml全部is_primer(直至sqrt(N))，假如is_primer[i]=true,则is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10，则
从4开始解析xml：
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://dongxicheng.org/structure/bitmap/
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) 储存方法提升
依然选用位图文件方法储存，只不过位图文件中只储存合数，那样一下子节约了一半室内空间（必须的室内空间仅为4g/(32*2)=64MB）
储存空间提升后，优化算法高效率也会提高许多 ，如：1,2，…,30
只需储存3,5,7,9,11,13,15,17,19,21,23,25,27,29
i=0, is_primer[0] =true, 把字符[3][6][9][12]，即9,15,21,27,标成false
i=1, s_primer[0] =true,把字符为[6][11],即15,25标成false
i=2, 2*i 3>sqrt(30),完毕
即：i=s, 把字符为s(2*t 1) 3t,在其中，t=1,2,3，…中全部的的is_primer置为false
(2) 提升筛选优化算法
a是素数，则下一个起始点是a*a,把后边的全部的a*a 2*i*a筛除。即贪求n之内的素数，就先把sqrt(n)内的素数求出去，用早已求取的素数来筛选后边的合数。
6. 小结
迄今截止，沒有所有人发觉素数的遍布规律性，也没人能用一个计算公式出全部的素数。有关素数的许多 的有意思的特性或是生物学家的勤奋，如：
(1) 高斯函数猜想，n之内的素数数量大概与n/ln(n)非常，换句话说，当n非常大时，二者量级同样。这就是知名的素数定理。
(2) 十七世纪费马猜想，2的2^n三次方 1，n=0，1，2…时是素数，那样的数叫费马素数，遗憾当n=5时，2^32 1就并不是素数，迄今都没有寻找第六个费马素数。
(3) 18世纪发觉的最大素数是2^31-1，十九世纪发觉的最大素数是2^127-1，二十世纪末人们已经知道的最大素数是2^859433-1，用十进制表明，这是一个258715位的数据。
(4) 孪生素数猜测：差为2的素数有无限多对。现阶段了解的较大 的孪生素数是1159142985×2^2304－1和1159142985×2^2304＋1。
(5) 歌德巴赫猜想：超过2的全部双数均是2个素数的和，超过5的全部合数均是三个素数之和。在其中第二个猜测是第一个的当然推理，因而歌德巴赫猜想又被称作1 1难题。我国数学家陈景润证实了1 2，即全部超过2的双数全是一个素数和仅有2个素数因素的合数的和。国际性上称之为陈氏定理。（节选自《http://chuanbindeng.blog.163.com/blog/static/67886226200982892139468/》）
7. 参考文献
http://www.doc88.com/p-5780302974.html
http://chuanbindeng.blog.163.com/blog/static/67886226200982892139468/
