プロジェクトオイラー＃3 Java：平方根からカウントダウンするのではなく、最大の素因数を見つけるときに、平方根にカウントするのはなぜですか？

Question

私はプロジェクトオイラーの問題3を解決しようとしていると私はそれ天気を思っていた私に パブリッククラス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=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)); 

}} 

を正しい答えを与え、次のコードを書かれているがで開始することをお勧めし1を計算し、平方根に向かって増加させます。だから私は、nの平方根から始まり、カウントダウンするように、largestPrimeFactor（long n）メソッドのforループを変更しようとしました。しかし、今私は間違った答えを得る。これの理由は何ですか？

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

最初の素因数を見つけてから休憩する必要はありません。最初に見つかったものが一番大きく、これ以上検索しないでください。そのために、あなたがこの

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; 
}