算法笔记(7)| 数学问题(1)

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;
        }
    }
}