小编Nuu*_*tti的帖子

我试图找到潜在因子素数的除数(形式n!+ - 1的数量),因为我最近买了Skylake-X工作站,我认为我可以使用AVX512指令加快速度.

算法简单,主要步骤是对同一个除数重复取模.主要是循环大范围的n值.这是用c写的天真的方法(P是素数表):

uint64_t factorial_naive(uint64_t const nmin, uint64_t const nmax, const uint64_t *restrict P)
{
uint64_t n, i, residue;
for (i = 0; i < APP_BUFLEN; i++){
    residue = 2;
    for (n=3; n <= nmax; n++){
        residue *=  n;
        residue %= P[i];
        // Lets check if we found factor
        if (nmin <= n){
            if( residue == 1){
                report_factor(n, -1, P[i]);
            }
            if(residue == P[i]- 1){
                report_factor(n, 1, P[i]);
            }
        }
    }
}
return EXIT_SUCCESS;
}

这里的想法是针对同一组除数检查大范围的n,例如1,000,000 - > 10,000,000.因此,我们将以数百万次对相同的除数进行模数尊重.使用DIV非常慢,因此根据计算范围有几种可能的方法.在我的情况下,n很可能小于10 …