数学问题归纳

最大公约数：

证明可知：a与b的最大公约数 与 b与 a%b 的最大公约数相同

int gcd(int a, int b){
    if(b == 0)
        return a;
    else
        return gcd(b, a % b);
}
           

最小公倍数：

已知a, b 求得的最大公约数为 c, 则最小公倍数为 ab / c

分数的四则运算：

代码模板：B1034/A1088 有理数四则运算 （20 分）（分数四则运算模板）（数学问题）

素数判断函数：

#include <cmath>
bool isPrime(int n){
  if(n <= 1)  return false;
  int sqr = (int)sqrt(1.0 * n);
  for(int i = 2; i <= sqr; i++){
    if(n % i == 0)
      return false;
  }
  return true;
}
           

质因子分解模板：

A1059 Prime Factors （25 分）（质因数分解）