文章目录

• 素数
• 合数
• 最大公约数

• GCD

• 最小公倍数
• 闰年

素数

别名，（质数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

合数

合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。

最大公约数

别名： 最大公因数

求两个整数最大公约数主要的方法：

1.穷举法：分别列出两整数的所有约数，并找出最大的公约数。

2.素因数分解：分别列出两数的素因数分解式，并计算共同项的乘积。

3.短除法：两数除以其共同素因数，直到两数互素时，所有除数的乘积即为最大公约数。

4.辗转相除法：两数相除，取余数重复进行相除，直到余数为0时，前一个除数即为最大公约数。

相关介绍： https://blog.csdn.net/Ljnoit/article/details/104730787

参考链接

GCD

• 手写

inline int gcd(int a,int b) {
    int r;
    while(b>0) {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

• gcd库函数

#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
  int k = __gcd(4,2);
  std::cout<<k; // k
  return  0;
}

最小公倍数

最小公倍数 = a*b / 最大公约数

闰年

n%4==0&&n%100!=0||n%400==0