如何在数字的素数因子分解中找到素数的多重性？

Question

我必须在所有数字中找到多个最小素数因子,直到10 ^ 7.我正在使用Eratosthenes的Sieve来找到所有素数.并且在一个单独的数组中,我存储了复合数的最小素因子.这是我的代码

 for(ull i=2;i<=m;i++)
{
    if (check[i])
    {
         uncheck[i]=true;
        for (ull k=i*i; k<=n; k+=i)
         {
           if(check[k]==true)
           phi[k]=g;
           check[k]=false;
         }  
    }

}

现在我正在运行一个循环,直到n并在其中使用循环来计算它.这是代码

 for(ull i=4;i<=n;i++)
{

    if(check[i]==false)
    {   
        ull count=0; 
        ull l=i;
         ull r=phi[i];
         while(l%r==0)
         {
            l=l/r;
            count++;
         }               
        cout<<count<<'\n';
    }


}

有没有更快的方法来计算这个？

Answer 1

当然,你可以在没有循环的情况下做到这一点.

c最多可能是64位.它不能包含超过63次以外的任何因子.因此,不是循环,而是编写63个嵌套的if语句.

对于j == 2的情况,您的编译器可能具有一些计算尾随零位的内部函数.如果是这种情况,那么你单独处理这种情况,你只需要40 if,因为3 ^ 41> 2 ^ 64.