每个合数都可以写成几個质数相乘的形式其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来叫做分解质因数如何求最大公因数。洳30=2×3×5 分解质因数如何求最大公因数只针对合数。

这样的分解称为$N$ 的标准分解式

以下将采用算数基本定理的标准分解式對数进行因式分解

欧拉数（小于$n$且与$n$互质的数的个数：

此处将总结三种筛选素数的方法：

遍历$2$~$N$以内的所有数，随后判斷这个数是否能被除$1$和自身以外的数整除

遍历$2$~$N$以内的所有数从$2$开始遍历，在此同时对$N$以内中所有$2$的倍数进行一个状态标记

• 2昰质数，而4,6,8,10,12…则是合数作标记
• 3是质数，而6,9,12,15…则是合数做标记
• 4已经被做标记，则不再做标记
• 5是质数而5,10，15,20,25…则是合数做标记