Échec du programme de factorisation des primes (C++)

Question

Je tente de résoudre le problème this lors de la programmation. Voici la question.

Les principaux facteurs de 13195 sont 5, 7, 13 et 29.

Quel est le plus grand facteur premier du nombre 600851475143?

Maintenant, j'ai concocté un programme C++, qui essaie de le vérifier par la force brute, cependant, lors de l'exécution de son coincé à 5. Voici le programme

#include <iostream> 
#include <math.h> 
using namespace std; 
const long long no = 600851475143; 

long long isprime(long long p) 
{ 
    long long reply = -1; 
    long long i = 2; 
    while (i < pow(p, 0.5)) { 
     if (i % p == 0) 
      reply = i; 
    } 
    if (reply == -1){ 
    return 0; 
    cout<<" yup its prime "<<endl; 
    } 

    else 
     return reply; 
} 

long long factor(long long x) 
{ 
    for (long long i = 2; i < no; i++) { 
    cout<<"Trying "<<i<<endl; 
     if ((isprime(i) == 0)&& (no % i == 0)) { 
      return i; 
     cout<<"found "<<i<<endl; 
      break; 
     } 
    } 
} 

int main() 
{ 
    long long ans = no; 
    while (ans != 1) { 
     cout << factor(ans) << endl; 
     ans = ans/factor(ans); 
    } 
} 

et c'est la sortie Je ne comprends vraiment pas pourquoi il est bloqué au numéro 5, quelqu'un peut-il m'aider?

EDIT: Merci b13rg, j'ai réalisé mon erreur. J'ai maintenant un meilleur algorithme, je l'ai collé pour tous ceux qui en ont besoin.

#include<iostream> 
#include<math.h> 
using namespace std; 

long long fun (long long x) 
{ 
    for(long long i=2; i<sqrt(x);i++){ 
    while (x%i==0){ 
     cout<<i<<endl; 
     x=x/i; 
     } 
    } 
} 

int main(){ 

fun(600851475143); 


return 0;} 

Answer 1

Vous semblez ne jamais modifier la valeur de i ou p dans la boucle while de la fonction isprime. Il échoue parce que sqrt (5) est plus grand que 2, et rien dans la boucle while ne change jamais.

Pour le problème que vous essayez de résoudre:

Vous pouvez d'abord optimiser la boucle de contrôle que par un nombre impair essayant, donc d'abord faire 2, puis 3, puis 5 etc. Pour rendre encore plus vite possible vous code dur dans les premiers nombres premiers, mais cela pourrait être au-delà de la portée de ce projet.

Pour trouver le plus grand facteur premier, vous devez d'abord trouver le plus petit facteur premier. Par exemple, dans le nombre ci-dessus, le plus petit est 5. L'étape suivante consisterait à diviser 13195 par 5 pour obtenir 2369. Puis recommencez pour trouver le plus petit facteur premier de ce nombre, et continuez jusqu'à ce que le résultat de division soit premier.

Number|Smallest prime 
------|-------------- 
13169 | 5 
2369 | 7 
377 |13 
29 |Largest prime factor of 13169