★前言：
众所周知，不管是在学习、考试还是以后找工作中，对于求解素数的问题随处可见，而且还是一个重难点，为何要说是重难点呢？主要是因为对于不同的人往往会有不同做法，但大多数掌握的都是一些非常平庸的做法，完全没有技术含量。然而这对于我们这些技术人员无疑是一个BIG BUG。所以小编在此整理了一些求解套路，如有疑问，欢迎来扰。
★试除法：
首先要介绍的，当然非"试除法"莫属啦。考虑到有些读者没听过，小编在此稍微解释一下：
"试除"，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是素数。
显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过呢，这个最平庸的思路，也有好多种境界。不信请看下文：
◎境界1//假设要判断 x 是否为质数，就从 2 一直尝试到 x-1。这种做法，其效率应该是最差的
#include#includeint main()
{
int i = 0,k = 0;
int count = 0;
for(i=100; i<=200; i++)
{
for(k=2; k
◎境界2//所有素数都是偶数，因此可以加快步长
#include#includeint main()
{
int i = 0, k = 0;
int count = 0;
for(i=101; i<=200; i+=2)
{
for(k=2; k
◎境界3//除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数
#include#includeint main()
{
int i = 0, k = 0;
int count = 0;
for(i=100; i<=200; i+=2)
{
for(k=2;k
◎境界4//其实只要从 2 一直尝试到√x，简单解释一下：如，100的因数有：1和100，2和50，4和25，5和20，10和10
#include #include int main()
{
int i = 0;
int count = 0;
for(i=100; i<=200; i++)
{
int j = 0;
for(j=2; j<=sqrt(i); j++)
{
if(i%j == 0)
break;
}
if(j>sqrt(i))
{
printf("%d ", i);
count++;
}
}
printf("\ncount = %d\n", count);
return 0;
}
◎境界5//对于任意一个素数n，如果它有两个质因子x，y，显然n =x*y， 所以，由不等式性质可得，x <= sqrt(n)， 即 x <= n^(1/2)。
#include #include int main()
{
int i = 0;
int count = 0;
for(i=101; i<=200; i+=2)
{
int j = 0;
for(j=2; j<=sqrt(i); j++)
{
if(i%j == 0)
break;
}
if(j>sqrt(i))
{
count++;
printf("%d ", i);
}
}
printf("\ncount = %d\n", count);
return 0;
}
★筛选法：
不知道的小伙伴请戳━>筛选法。筛选法 ，真的是一个既巧妙又快速的求质数方法。其发明人是公元前250年左右的一位希腊大牛——埃拉托斯特尼。为什么说他是大牛捏？因为他本人精通多个学科和领域，至少包括：数学、天文学、地理学(地理学这个词汇，就是他创立的)、历史学、文学(他是一个诗人)。真的堪称"跨领域的大牛"。估计很多人把筛法仅仅看成是一种具体的方法。其实，筛法还是一种很普通的思想。在处理很多复杂问题的时候，都可以看到筛法的影子。那么，筛法如何求质数捏，说起来很简单：
先解释一下筛选法的步骤：
<1> 先将1挖掉(因为1不是素数)。
<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> 用3去除它后面的各数，把3的倍数挖掉。
<4> 分别用5…各数作为除数去除这些数以后的各数。
上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的倍数大于1的全部置0，3的倍数大于1的全部置0，4的倍数大于1的全部置0.。。。一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找就好了
光说不练假把式，贴出代码：
#includeint main()
{
int i,j,a[100],e;
for(i=0;i<100;i++)
a[i]=i+1;
for(i=0;i<100;i++)
{
j=i-1;
while(j>1)
{
e=a[i]%j;
if(e==0)a[i]=0;
j=j-1;
}
}
for(j=1;j<100;j++)
{
if(a[j]!=0)
{
printf("%2d ",a[j]);
}
}
return 0;
}
●确定质数的分布范围
估计素数个数求解公式x/ln(x)(素数定理)误差小于15%范围越大，误差越小
●存储容器
境界1(构造整形容器)
100~200所有素数，除去所有合数剩下的就是素数
思想：筛去2,3,5，7,11,13的倍数，剩下的就是素数
境界2(布尔型容器)
境界3(按位(bit)存储)
小编目前还是菜鸟级别，如有不正之处，欢迎批评指正！
