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的这段代码有什么问题？

回答

相关问题