Project Euler#3的这段代码有什么问题？

Question

#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问题3编写的代码.我不明白为什么当我跑它时,它给了我1471.这是一个很好的答案,但不是最大的.但如果我改变i = 1471它给我正确的答案6857 ...问题出在哪里？为什么它不是"自动地"给我好的6857答案但1471从2开始？

PS.我知道我不必long long到处使用.

Answer 1

你的因子分解算法需要在C和之间进行选择A,因为在进程结束时A包含余数,这也是原始因子A.如果碰巧是最大的那个,你的代码会错过它.

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

完成此修改后,您的代码将生成正确的答案(演示).

注意:既然您的程序正在运行,您可以考虑进行一些修改:

• 尝试潜在的除数直到达到A/2效率低下; 你可以停在平方根(你明白为什么？)
• 在构建程序的方式中不需要检查素数
• 通过尝试所有数字(即数学定义的方式)来检查素数是非常低效的:你正在尝试过多的除数,这些除数保证不起作用.同样,你可以停在平方根.如果从2开始,而不是1开始,停在平方根处,找不到除数,则数字为素数.