Cosa c'è di sbagliato con questo codice per 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; 
} 

Questo è il codice che ho fatto per Project Euler problem 3. Non capisco perché quando lo eseguo, mi dà 1471. È una buona risposta ma non la più grande. Ma se cambio i = 1471 mi dà la risposta corretta 6857 ... Dov'è il problema? Perché non "automagicamente" mi dà la buona risposta 6857 ma 1471 quando parto da 2?

PS. So che non devo usare long long ovunque.

Answer 1

l'algoritmo di fattorizzazione deve scegliere tra C e A, perché alla fine del processo A contiene il resto, che è anche un fattore dell'originale A. Se capita di essere il più grande, il tuo codice lo mancherebbe.

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

Una volta effettuata questa modifica, il codice produce la risposta corretta (demo).

Nota: ora che il programma è in esecuzione, si può prendere in considerazione un paio di modifiche:

• Provando potenziali divisori fino a raggiungere A/2 è inefficiente; puoi fermarti alla radice quadrata (vedi perché?)
• Il controllo della primalità non è richiesto nel modo in cui hai strutturato il tuo programma
• Controllare la primalità provando tutti i numeri, cioè il modo in cui la definizione matematica va, è grossolanamente inefficiente: stai provando troppi divisori che sono garantiti per non funzionare. Di nuovo, puoi fermarti alla radice quadrata. Se inizi a 2, non a 1, fermati alla radice quadrata e non trovi divisori, il numero è primo.