某些數字比其他數字需要更長的時間

有人能告訴我數字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; 
}

來源

2013-05-20 0x41414141

也許是因爲'104751475143'有很多小的因素需要拔出？ – Mysticial

「有些數字比其他數字需要更長的時間」 - 確切地說，您是否認爲可以在相同的時間內分解所有可能的數字？ – 2013-05-20 05:18:56

@ H2CO3以及我認爲更大的數字需要更長的時間。看起來它主要與我的實例中的平方根有多接近。 – 0x41414141

它需要更長的時間，因爲104751475143的主要因素是391751和391751分之104751475143= 267393比3更接近104751475143平方根（3 =83825047分之251475141）接近的251475151平方根所以它必須通過循環的更多迭代。

來源

2013-05-20 05:36:06 0x41414141

某些數字比其他數字需要更長的時間

回答

相關問題