Project Euler＃3的這段代碼有什麼問題？

#include <iostream> 

using namespace std; 
int prim(long long x) { 
    int s = 0; 
    for(long long i = 1; i <= x ; i++) { 
     if(x % i == 0) { 
      s++; 
     } 
    } 
    if(s == 2) { 
     return 1; 
    } 
    return 0; 
}

int main() { 
    long long A = 600851475143; 
    long long i = 2; 
    long long C = 0; 

    while(i < (A/2)) { 
     while(A % i == 0 ) { 
      A = A/i; 
      if(i > C) { 
       C = i; 
      } 
     } 
     i++; 
    } 
    if(prim(C)) { 
     cout<<C; 
    } 

    return 0; 
}

這是我爲Project Euler problem 3使得代碼。我不明白爲什麼當我運行它時，它給了我1471.這是一個很好的答案，但不是最大的答案。但如果我改變i = 1471它給了我正確的答案6857 ...問題在哪裏？爲什麼它不是「自動地」給我6857的答案，而是從2開始的1471答案？Project Euler＃3的這段代碼有什麼問題？

PS。我知道我不必在任何地方都使用long long。

來源

2014-04-04 user3498710

任何你需要這麼多行的理由？這迫使我滾動更多，我討厭，特別是因爲我有兩個滾動條在對方內，這使得它真的很不舒服。 – Deduplicator

用較少的行推動編輯。 – Whitebird

@Deduplicator你總是可以讓別人爲你滾動 – 4pie0

您的分解算法需要在C和A之間選取，因爲在該過程結束時A包含餘數，這也是原始A的一個因子。如果它碰巧是最大的，你的代碼會錯過它。

if (A > C) { 
    C = A; 
}

一旦進行這種修改，你的代碼產生正確答案（demo）。

注：現在你的程序正在運行，你可以考慮做一些修改：

，直到你達到A/2是低效的試行潛在除數;你可以在平方根停止（你知道爲什麼嗎？）
檢查素性在你已經結構化的程序
通過嘗試所有的數字檢查素性的方式不是必需的，即數學定義的方式去，是非常低效的：你嘗試了太多的保證不起作用的因子。再次，你可以停在平方根。如果從2開始，而不是1，則停在平方根處，並且找不到任何除數，數字爲素數。

來源

2014-04-04 15:36:29 dasblinkenlight

或者，如果（prim（C））cout << max（A，C）;' – Mohammad

Project Euler＃3的這段代碼有什麼問題？

回答

相關問題