Projet Euler # 3 Java: Pourquoi compter jusqu'à la racine carrée pour trouver le plus grand facteur premier, plutôt que de compter à partir de la racine carrée?

Question

Je suis en train de résoudre le problème 3 du projet Euler et j'ai écrit le code suivant qui me donne la bonne réponse LargestPrimeFactor public class {

public static boolean isPrime(int p) { 
    boolean isPrime = true; 
    for (int i = 2; i < p/2; i++) { 
     if (p % i == 0) { 
      return false; 
     } 
    } 
    return isPrime; 
} 

public static double largestPrimeFactor(long n) { 
    double factor = 0; 

    for (int j=1; j<Math.sqrt(n); j++) { 
     System.out.println("j is : "+ j); 
     if (n % j == 0 && isPrime(j)) { 
     factor = j; 
     } 
    } 
    return factor; 
} 


public static void main(String args[]) { 
    long limit = 600851475143L; 
    System.out.println(largestPrimeFactor(limit)); 

}} 

Je me demandais wether c'est une bonne idée de commencer à 1 et augmenter vers la racine carrée, lorsque nous cherchons le plus grand facteur. J'ai donc essayé de changer la boucle for dans la méthode largerPrimeFactor (long n) pour démarrer à partir de la racine carrée de n et compter à rebours. Cependant maintenant je reçois une réponse incorrecte. Quelle est la raison pour ça?

public class LargestPrimeFactor { 

public static boolean isPrime(int p) { 
    boolean isPrime = true; 
    for (int i = 2; i < p/2; i++) { 
     if (p % i == 0) { 
      return false; 
     } 
    } 
    return isPrime; 
} 

public static double largestPrimeFactor(long n) { 
    double factor = 0; 

    for (int j=(int)Math.sqrt(n); 1<j; j--) { 
     System.out.println("j is : "+ j); 


     if (n % j == 0 && isPrime(j)) { 
      factor = j; 
     } 

    } 
    return factor; 
} 

public static void main(String args[]) { 
    long limit = 600851475143L; 
    System.out.println(largestPrimeFactor(limit)); 

}} 

Answer 1

Vous n'avez pas de pause après avoir trouvé le premier facteur premier - le premier que vous trouvez est le plus grand et vous ne devriez pas chercher plus loin. Pour cela, vous devriez retourner la première valeur correcte que vous trouvez comme ceci

public static double largestPrimeFactor(long n) { 
    double factor = 0; 

    for (int j=(int)Math.sqrt(n); 1<j; j--) { 
     if (n % j == 0 && isPrime(j)) { 
      return j; // Changed this line 
     } 

    } 
    return factor; 
}