欧拉函数:求小于等于n且与n互质的数的个数
求小于等于n且与n互质的数的个数
互质穷举法
互质:两个数互质代表两者最大公约数为1
最大公约数求法:辗转相除法,最小公倍数:较大值除以最大公约数乘以较小值
辗转相除法:
较大的数a取模较小的数b,得取模值c
若取模值等于0 则最大公约数为取模值,否则继续下一步
a与c再次取模,回到第二步
//求最大公约数gcd以及最大公倍数lcm
// 36 24 36/24
// 24 12 24/12
// 0 结束最大公约数为12
// 求最小公倍数
// lcm(a, b) = (a * b)/g