數學問題歸納

最大公約數：

證明可知：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 分）（質因數分解）