Điều gì sai với mã này cho 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; 
} 

Đây là mã tôi đã thực hiện cho Project Euler problem 3. Tôi không hiểu tại sao khi tôi chạy nó, nó mang lại cho tôi 1471. Đó là một câu trả lời hay nhưng không phải là câu trả lời lớn nhất. Nhưng nếu tôi thay đổi i = 1471 nó mang lại cho tôi câu trả lời đúng 6857 ... Vấn đề ở đâu? Tại sao nó không "automagically" cho tôi câu trả lời 6857 tốt nhưng 1471 khi tôi bắt đầu từ 2?

PS. Tôi biết tôi không phải sử dụng long long ở mọi nơi.

Answer 1

Thuật toán yếu tố hóa của bạn cần chọn giữa C và A, vì vào cuối quá trình A chứa phần còn lại, cũng là một yếu tố của số A gốc. Nếu nó là một trong những lớn nhất, mã của bạn sẽ bỏ lỡ nó.

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

Khi bạn thực hiện sửa đổi này, mã của bạn sẽ đưa ra câu trả lời đúng (demo).

Lưu ý: bây giờ mà chương trình của bạn đang chạy, bạn có thể xem xét một vài sửa đổi:

• Thử ước tiềm năng cho đến khi bạn đạt A/2 là không hiệu quả; bạn có thể dừng lại tại căn bậc hai (bạn có thấy tại sao?)
• Kiểm tra tính nguyên thủy không cần thiết theo cách bạn đã cấu trúc chương trình của mình
• Kiểm tra tính nguyên thủy bằng cách thử tất cả các số, tức là cách định nghĩa toán học đi, là rất kém hiệu quả: bạn đang cố gắng quá nhiều ước chia được đảm bảo không hoạt động. Một lần nữa, bạn có thể dừng lại ở căn bậc hai. Nếu bạn bắt đầu ở 2, không phải ở 1, dừng lại ở căn bậc hai, và không tìm thấy ước số, số đó là số nguyên tố.