UC知道关于C＋＋求素数
来源：百度知道 编辑：UC知道 时间：2024/05/09 07:45:15
//编程求50～100内的素数
#include <iostream>
using namespace std;
#define min 51
#define max 100
void main ()
{
int i,j;
for(i=min;i<=max;i+=2)
{
for(j=2;j<i;j++)
if(i%j==0)
break;
if(i==j)cout<<i<<" ";
}
}
for(j=2;j<i;j++)这里的j<i可以改成j<i/2，这是为什么啊
为什么只要算一半就可以了
还有一种算法是开方的，为什么啊
#include <iostream>
using namespace std;
#define min 51
#define max 100
void main ()
{
int i,j;
for(i=min;i<=max;i+=2)
{
for(j=2;j<i;j++)
if(i%j==0)
break;
if(i==j)cout<<i<<" ";
}
}
for(j=2;j<i;j++)这里的j<i可以改成j<i/2，这是为什么啊
为什么只要算一半就可以了
还有一种算法是开方的，为什么啊
开方的是效率最高的
比如16
它的因数有1 2 4 8 16
判断它能不能被其他数整除其实只要算到4就可以了
因为
1*16=16
2*8=16
4*4=16
8*2=16
16*1=16
这样看比较清晰吧
4*4以下的都是重复的了，没有必要再去管了
所以只要算到平方根就可以了
算到一半也行，不过要比平方根算的多了点
是否是素数是用比它小的数去除它看能否出尽来判断的，而如果能出尽的话那么除数是成对存在的，比如22=2*11，2和11就是一对，而这一对只要判断一个就可以了，因此这种除数判断的下界为2，而上界为被除数开根号。 至于i/2这个运算的更多，里面有一部分是不需要的。