c语⾔求最⼤质数,【C语⾔】求解素数（质数）的N种境界★前⾔：
众所周知，不管是在学习、考试还是以后⼯作中，对于求解素数的问题随处可见，⽽且还是⼀个重难点，为何要说是重难点呢？主要是因为对于不同的⼈往往会有不同做法，但⼤多数掌握的都是⼀些⾮常平庸的做法，完全没有技术含量。然⽽这对于我们这些技术⼈员⽆疑是⼀个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;
c++判断素数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)存储)
⼩编⽬前还是菜鸟级别，如有不正之处，欢迎批评指正！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。