c++ - 如何在数的质因数分解中找到质因数的重数？

Question

我必须找到所有数字中最小素因数的重数，直到 10^7。我正在使用埃拉托斯特尼筛法来查找所有素数。在一个单独的数组 phi 中，我存储合数的最小质因数。这是我的代码

 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 位。它包含除 1 以外的任何因子的次数不得超过 63 次。因此，您可以编写 63 个嵌套的 if 语句，而不是循环。

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