프로젝트 오일러 # 3 자바 : 제곱근을 줄이는 것이 아니라 가장 큰 소수 요소를 찾을 때 제곱근까지 세는 이유는 무엇입니까?

Question

나는 프로젝트 오일러의 문제 삼을 해결하기 위해 노력하고있어 나는 나에게 정답 공용 클래스 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이고 우리가 가장 큰 요인을 찾을 때 제곱근쪽으로 증가합니다. 그래서 가장 큰 PrimeFactor (long n) 메서드의 for 루프를 n의 제곱근에서 시작하여 카운트 다운하도록 변경하려고했습니다. 그러나 지금 나는 틀린 대답을 얻는다. 이것에 대한 이유는 무엇입니까?

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