1.最大公约数与最小公倍数
1.最大公约数
最大公约数是指正整数a和b中都能够除尽的最大的数。解决最大公约数是方法一般是基于欧几里得算法：gcd(a,b)=gcd(b,a%b)。
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
2.最小公倍数
最小公倍数是指正整数a和b中，都能被除尽的最小的数。解决该问题的是在最大公约数的基础上进行的。假设a和b的最大公约数为d，则二者的最小公倍数为ab/d。
2.分数
1.分数的表示和化简
1.分数的表示
分数一般是采用创建一个结构体来表示，结构里面包含分数的分子和分母。
struct Fraction{
int up; //分子
int down; //分母
};
2.分数的化简
分数的化简主要满足三项规定：
1）如果分母down为负数，那么令分子up和分母down都变为相反数
2）如果分子up=0，则让down=1
3）约分：求出up和down的最大公约数d，然后让分子和分母同时除以d
Fraction reduction(Fraction result){
if(result.down<0){
result.up=-result.up;
result.down=-result.down;
}
if(result.up==0){
result.down=1;
}
else{
int d=gcd(abs(result.up),abs(result.down)); //求解最大公约数
result.up=result.up/d;
result.down=result.down/d;
}
return result;
}
3.分数的输出
对于分数的输出，需要注意以下几点：
1）输出分数前，需要对其进行化简
2）如果分数的分母为1，则表示该分数为整数，输出时直接输出分子即可
3）如果该分数为真分数，则应该按照带分数的各式输出
void showResult(Fraction r){
r=reduction(r); //化简
if(r.down==1){
printf("%d",r.up);
}
else if(abs(r.up)>abs(r.down)){
printf("%lld %lld/%lld",r.up/r.down,abs(r.up)%r.down,r.down);
}
else{
printf("%d/%d",r.up,r.down);
}
}
3.素数
1.判断素数
bool isPrime(int a){
int sqr=(int)sqrt(1.0*a);
if(a==1) return false;
for(int i=2;i<sqr;i++){
if(a%i==0){
return false;
}
}
return true;
}
2.获取素数表
const int maxn=101;
int prime[maxn],pNum=0;
bool p[maxn]={false};
void Find_Prime(){
for(int i=1;i<maxn;i++){
if(isPrime(i)){
prime[pNum++]++;
p[i]=true;
}
}
}
