UC知道关于C++求素数的小问题
来源：百度知道 编辑：UC知道 时间：2024/06/01 08:19:51
看下面这段代码：
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
void main()
{
//输入
long a,b,l=0;
cout <<"please input two numbers:\n";
cin >>a >>b;
cout <<"primes from " <<a <<" to " <<b <<" is:\n";
//处理
if(a%2==0) //若为偶数，则增1
a++;
for(long m=a; m<=b; m+=2){ //步长为2
int sqrtm=sqrt(m);
int i;
for(i=2; i<=sqrtm; i++) //判明素数
if(m%i==0)
break;
//输出
if(i>sqrtm){ //素数
if(l++%10==0)
cout <<endl;
cout <<setw(5) <<m;
}
}
}
其中“if(i>sqrtm){ //素数”是什么意思？我弄不明白为什么要这样，但我若去掉这一步却又不对。请知道能告诉我一下吗……？
非常感谢！
两位的答案差不多，但可能我较笨，还没弄懂为什么当i>sqrtm时，m 就是素数呢，能再说得再好些吗……？
谢谢……！！
#include <iostream.h>
#include <iomanip.h>
#include <math.h>
void main()
{
//输入
long a,b,l=0;
cout <<"please input two numbers:\n";
cin >>a >>b;
cout <<"primes from " <<a <<" to " <<b <<" is:\n";
//处理
if(a%2==0) //若为偶数，则增1
a++;
for(long m=a; m<=b; m+=2){ //步长为2
int sqrtm=sqrt(m);
int i;
for(i=2; i<=sqrtm; i++) //判明素数
if(m%i==0)
break;
//输出
if(i>sqrtm){ //素数
if(l++%10==0)
cout <<endl;
cout <<setw(5) <<m;
}
}
}
其中“if(i>sqrtm){ //素数”是什么意思？我弄不明白为什么要这样，但我若去掉这一步却又不对。请知道能告诉我一下吗……？
非常感谢！
两位的答案差不多，但可能我较笨，还没弄懂为什么当i>sqrtm时，m 就是素数呢，能再说得再好些吗……？
谢谢……！！
这里计算素数的原理你要先弄清楚，就是从2开始，一直到该数的平方根之间的所有整数，如果都不可以被该数整除，那么该数就是素数。
所以循环从2到sqrtm（该数的平方根），如果发现整除（m%i==0）便跳出循环，所以再循环后需要对i与平方根的大小进行判断，如果i还小于平方根，说明循环是由于有整除条件成立break出来的，相反如果i大于平方根，则说明循环已经彻底执行完毕没有达到整除的条件成立，也就是说是素数。
首先提醒下你写错了。sqrt（）函数是求平方根的函数。应该这样调用sqrt(m).
素数也称质数，只有能被1和本身整除的数都称为素数。
如果你去掉if(i>sqrt(m))这部肯定不对，原因在于这里i对上面的FOR循环做判断，如果FOR循环在i<sqrt(m)内结束的话，说明他还能被其他数整除，根据定义那么不是素数。如果i>sqrt(m)，则为素数。这样你该明白了吧？
至于为什么要用sqrt(m)来判断是否为素数，简单的说，这是一种数学上的算法，比直接用定义判断要简单的多。
两位的答案差不多，但可能我较笨，还没弄懂为什么当i>sqrtm时，m 就是素数呢，能再说得再好些吗……？
if(i>sqrtm)就是判断在上面循环是不是中途跳出循环。i>sqrtm就表示循环不是中途跳出循环的。