许多算法都涉及数论中的知识,掌握了公式,可以很快速进行求解。
1.最大公约数
1) 辗转相除法
我们直接上代码
int gcd(int m, int n){
int ans = m % n;
while(ans != 0){
n = ans;
m = n;
ans = m % n;
}
return ans;
}
2) 递推算法
int gcd(int a, int b){
if(b == 0){
return a;
}else{
return gcd(a, a%b);
}
}
3)算法复杂度最低的算法
int gcd(int a, int b){
if(!a) return b;
if(!b) return a;
if(a&1==0 && b&1==0){
return gcd(a>>1,b>>1)<<1;
}else if(a&1==0) return gcd(a>>1,b);
else if(b&1==0) return gcd(a,b>>1);
else return gcd(Math.abs(a-b), Math.min(a, b));
}
2.判断是否为素数
1)常用方法
bool func(int n){
for(int i=2;i<= Math.sqrt(n); i++){
if(n%i == 0) return false;
}
return true;
}
网友评论