867.分解质因数

void divide(int n)
{
    for(int i=2;i<=n/i;i++)//n中最多包含一个大于sqrt(n)质因数，所以这里先把小于等于根号n的质因数枚举出来
    {
        if(n%i==0)//枚举到一个质因数时
        {
            int s=0;
            while(n%i==0)
            {
                s++;   //就判断它有说到次方
                n/=i;
            }
            printf("%d %d",i,s);
            cout<<endl;
        }

    }
    if(n>1) cout<<n<<" "<<1<<endl;//细节
}

870.约束个数

void get_yushu(int n)
{
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0) 
        {
            while(n%i==0)
            {
                primes[i]++;
                n/=i;
            }
        }
    }
    if(n>1) primes[n]++;//n分解质因数最后不为1的话，肯定最后还剩一个较大的素数，细节
}