首页 > 代码库 > 最大公约数，最小公倍数，素数，素数筛
最大公约数，最小公倍数，素数，素数筛
最大公约数
a、b的最大公约数是b,a%b的公约数，如果有一个等于0，最大公约数是a
int gcd(int a,int n){
if (b==0)
return a;
else
return gcd(b,a%b);
}
或
return b!=0 ? gcd(b,a%b):a;
最小公倍数
是两数的乘积除以他们的最大公约数
素数筛
输出2-10000之间的所有素数
从2开始遍历，标记每个数的所有倍数为非素数
void sushu(){
for (int i=0;i<10000;i++){
mark[i]=false;
}
size=0;
for (int i=2;i<10000;i++){
if (mark[i]==true)
continue;
//下面其实就是上面if的else
prime[size++] = i;
for (int j=i*i;j<10000;j+=i)
//j从i*i开始能够节约时间，因为2i，3i，，，ki(k<i)都被标记过了
mark[j]=true;
}
}
最大公约数，最小公倍数，素数，素数筛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。