1、了解质因数

• 质因数(素因数或质因子) 在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。只有一个质因子的正整数为质数。——百度
• 合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
• 每个合数都可以写成几个质数相乘的形式 ，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。 eg.3 是9的一个因数，3就是9的质因数，3也一定是质数
• 举个例子：
• 1没有质因子。
• 5只有1个质因子，5本身。（5是质数）
• 6的质因子是2和3。(6 = 2 × 3)
• 2、4、8、16等只有1个质因子：2。（2是质数，4 =2²，8 = 2³，如此类推）
• 10有2个质因子：2和5。(10 = 2 × 5)

2、质因数求法 O(logn ~ $\sqrt{n}$)

• 分解质因数只针对合数。求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
• 最多只有一个大于$\sqrt{n}$的质因子

代码

void divide(int n)
{
    for(int i=2;i<=n/i;i++)
    //如果满足，则i一定是质因数，因为合数拆分乘积就是质因数相乘
        if(n%i==0)//从2开始（根据图，如果满足就会一直除）
        {
            int s=0;
            while(n%i==0)//一直除，并且记录指数
            {
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
//因为n中最多只包含一个大于根号n的质因子,如果n>1表示这个数没有被除尽，则这个数为素数，只有1和它本身
        if(n>1)printf("%d %d\n",n,1);
        puts("");
}