1 .素数判断问题
素数判断问题是一个非常常见的问题，本文介绍了几种常用的判断方法。
2 .原始算法
素数的定义是可以被1和它自己整除，但不能被其他任何数整除的数。 根据素数的定义只需要将n除以2到n-1，如果都不能被整除，n就是素数，否则，只要其中有一个能被整除的数，n就不是素数。
boolis_primer1(intnum ) {
int i；
for(I=2； i num； I ) {
if(num%I==0) {
返回真；
}
}
返回假；
}
3 .算法改进
如果n不是素数，n可以表示为a*b。 其中，如果2=a=b=n-1，则必须满足a、b中的一个数。 1
boolis_primer2(intnum ) {
int i；
intupper=sqrt(num；
printf(primer2:%d(n )，upper )；
for(I=2； i=upper； I ) {
if(num%I==0) {
返回真；
}
}
返回假；
}
4 .筛选算法
更有效地判断素数的方法应该是将素数存储在一个素数表中，然后在判断一个数是否是素数时直接检查表。 这种方法需要解决两个问题。
)1)如何快速拿到质量法？ (采用筛选方法) ) ) ) ) ) ) )。
)2)如何减少质量法的大小？ (采用位图数据结构)
对于从1到n的所有整数，逐一判断它们是否是素数，找到一个不是素数的，把它挖出来，最后剩下的就是素数。 具体方法是：
1定义is_primer[i]=true；
从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
为了减少内存利用率，该算法使用了位图数据结构。 有关位图的信息，请参见https://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；
}
}
intupper=sqrt(int_max )；
for(I=1； i=upper； I ) {
if(test ) I ) }
for(j=II； j INT_MAX； j =i )
set(I；
}
}
}
用boolis_primer3(longnum )//查找表判断是否是素数
if (测试) num ) )
返回真；
返回假；
}
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 * i3 sqrt (30 )，退出
即，令i=s，下标为s(2*t1 ) 3t，这里，令t=1、2、3、的所有is_primer为false
)2)优化筛选算法
a是素数，下一个起点是a*a，筛掉后面所有的a*a 2*i*a。 也就是说，要求n以内的素数，首先要求sqrt(n )内的素数，用已经求出的素数筛选后面的次数。
6 .总结
到目前为止，没有人发现素数的分布规律，也没有人能用一个公式计算所有的素数。 关于质数的很多有趣的性质和科学家的努力，例如：
) jjdxh推测n以内的素数的个数与n/ln(n )大致相同，或者，如果n大，则两者为相同数量级。 这就是有名的质数定理。
)2)十七世纪的费马推测2的2^n次幂为1，n=0，1，2…时为素数。 这种数被称为费马素数，可惜当n=5时，2^32不是素数，至今仍未找到第6个费马素数。
(3) 18世纪发现的最大素数为2 ^ 31-1，19世纪发现的最大素数为2 ^ 127-1，20世纪末人类已知的最大素数为2^859433-1，用十进制表示为258715位数字。
)4)双胞胎素数猜想：差异为2的素数有无限多的一对。 现在知道的最大双胞胎素数是11591429852^2304-1和11591429852^2304 1。
(5)哥德巴赫猜想：所有大于2的偶数是两个素数之和，所有大于5的奇数是三个素数之和。 其中第二个猜想是第一个自然推理，因此哥德巴赫的猜想也被称为1 1个问题。 我国数学家陈景润证明，1 2即大于2的偶数都是一个素数和只有两个素数因子的数之和。 国际上被称为陈氏定理。