c - 有些数字比其他数字需要更长的时间来考虑

Question

有人能告诉我为什么数字 104751475143 的计算时间不到一秒，而数字 251475141 的计算时间更长吗？该代码试图找到最大的因素。

这是我的代码。

    long long lrgPFactor = 0;
    long long currentfactor = 0;
    long long tempfactor = 0;
    long long Number =  251475141;
    long long factor = 0;


    switch ((long long)sqrt(Number)%2) //skipping to the square root of the number to save time
{ 
    case 0: factor=((long long)sqrt(Number)-1); break; //If even make it odd
    default: factor=((long long)sqrt(Number)); break; //If odd leave it
}
    while (factor > 0) 
{
        if (Number % factor == 0) //if factor is a factor
       {
            factor=Number/factor; //make the factor the larger of the pair
        switch ((long long)sqrt(factor)%2) //same as above
            { 
                case 0: tempfactor=((long long)sqrt(factor)-1); break; 
                default: tempfactor=((long long)sqrt(factor)); break; 
            }  
            for (tempfactor = factor - 1; tempfactor > 1; --tempfactor) //simple way to determine if prime
            {
            if (factor % tempfactor == 0)
                    break;
            }
            if (tempfactor == 1)
            {
               lrgPFactor = factor;
               break;
           }
        }
        factor -= 2;
}

Answer 1

它需要更长的时间，因为 104751475143 的素数因子是 391751 和 104751475143/391751=267393 比 3 (3=251475141/83825047) 更接近 251475151 的平方根，因此它更接近于 104751475143 的平方根。循环的迭代。