2024-08-19 10:28 Bremerhaven H: Hochschule Bremerhaven 算法工程师 发布于浙江
关注
美团 0817笔试
最大公约数那道题，为什么这个代码不对呀。举例114的答案是112.因为114与112的最大公约数是2，2是素数。
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0) return b;
else{return gcd(b,a%b);}
}
bool ispre(int a){
if(a==1 ||a==4) return false;
if(a==2 || a==3) return true;
for(int i=2;i<a;i++){
if(a%i==0) return false;
}return true;
}
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
int m;
for(m=n;m>=2;m--){
//if(n%m==0 && ispre(m)) {cout<<m<<endl;break;}
int g=gcd(n,m);
if(ispre(g)){cout<<m<<endl;break;}
}
}
}
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(a%b==0) return b;
else{return gcd(b,a%b);}
}
bool ispre(int a){
if(a==1 ||a==4) return false;
if(a==2 || a==3) return true;
for(int i=2;i<a;i++){
if(a%i==0) return false;
}return true;
}
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
int m;
for(m=n;m>=2;m--){
//if(n%m==0 && ispre(m)) {cout<<m<<endl;break;}
int g=gcd(n,m);
if(ispre(g)){cout<<m<<endl;break;}
}
}
}
全部评论
胜九天
华中科技大学 C++
for初始化m=n。。。。。。
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享