C++：編程來查找數字的最大素數因子，我的代碼中出了什麼問題？

Question

這應該找到一個數的最大素因子..但它不工作.. 答案應該是6857，但它返回688543 ..

int isPrime(unsigned long int n) 
{ 
    for(unsigned long int i=2;i*i<(n);i++) 
    { 
     if(n%i==0) 
     { 
      return 0; 
      break; 
     } 
    } 
    return 1; 
} 

int main() 
{ 
    unsigned long int num=600851475143; 
    unsigned long int max=2, i=2; 
    while(num!=1) 
    { 
     if(num%i==0 && isPrime(i)) 
     { 
      max=i; 
      num/=i; 
      i--; 
     } 

     i++; 
    } 
    cout<<max; 
    return 0; 
} 

感謝提前:)

Answer 1

在其他問題，這將是有大量的問題：

for(unsigned long int i=2;i*i<(n);i++) 

i*i對於大量溢出爲unsigned long（這似乎是你的編譯系統上32位）。

您可以通過切換它解決它：

for (unsigned long int i = 2; i <= sqrt(n); ++i) 

只要n沒有溢出，則sqrt(n)將是有效的。不過，如果您打算使用非常接近32位整數範圍的數字，我仍然會建議您使用unsigned long long。

Answer 2

unsigned long顯然是你的系統上的32位，所以num將不是600851475143而是600851475143 mod 1<<32這是3851020999。 688543是這個數字的最大素數因子，所以看起來您的算法至少可以正常工作。

查找編譯器/系統組合類型的最大範圍，然後選擇合適的範圍。