매우 큰 소수 요소는 어떻게 결정합니까?

Question

그래서 저는 Euler 프로젝트에서 3 번 질문에 대한 답을 찾고자합니다. 나는 주어진 숫자의 가장 큰 소수 요소를 결정할 필요가있다.

프로젝트 오일러 : "13195의 소수 요소는 5, 7, 13 및 29입니다. 숫자 600851475143의 가장 큰 소수 요소는 무엇입니까?"

나는 내 코드를 작성했으며 int 크기만큼 완벽하게 작동합니다. 그러나 거대한 번호로 인해, 제 코드에는 변환 문제가 있습니다.

원래 나는 긴 변수와 긴 배열로 전환하려하지만 오류를 얻을 : '가능한 손실 변환을 긴에서 int로'

을 그래서 난 내 코드가 매우 긴 숫자를 수용 할 수있는 방법? PE에서 추가 예 :

public class Test { 

long[] delers; 

public static void main(String[] args) { 
    Test test = new Test(); 
    test.determineDividers(600851475143,determineNumberOfDividers(600851475143)); 
    long a = test.determineHighestPrime(test.delers); 
    System.out.println(a); 
} 

public void determineDividers(long getal,long aantalDelers) { 
    delers= new long[aantalDelers]; 
    long k = 0; 
    for (long i = 1; i < getal; i++) { 
     if (getal % i == 0) { 
      delers[k]=i; 
      k++;     
     } 
    } 
} 

public long determineNumberOfDividers(long getal) { 
    int k = 0; 
    for (long i = 1; i < getal; i++) { 
     if (getal % i == 0) { 
      k++;    
     } 
    } 
    return k; 
} 

public boolean determinePrime(long getal) { 
    for (long i = 2; i < getal; i++) { 
     if (getal % i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

public long determineHighestPrime(long[] deler) { 
    for (long i = deler.length - 1; i > 0; i--) { 
     if (determinePrime(deler[i]) == true) { 
      return deler[i]); 
     } 
    } 
    return 0; 
} 

}는 시간

EDIT 1 주셔서 감사합니다.

편집 2 : 추가 솔루션

public class Test { 

long[] delers; 

public static void main(String[] args) { 
    Test test = new Test(); 
    test.determineDividers(600851475143L,test.determineNumberOfDividers(600851475143L)); 
    long a = test.determineHighestPrime(test.delers); 
    System.out.println(a); 
} 

public void determineDividers(long getal,int aantalDelers) { 
    delers= new long[aantalDelers]; 
    int k = 0; 
    for (long i = 1; i < getal; i++) { 
     if (getal % i == 0) { 
      System.out.println(i); 
      delers[k]=i; 
      k++;     
     } 
    } 
} 

public int determineNumberOfDividers(long getal) { 
    int k = 0; 
    for (long i = 1; i < getal; i++) { 
     if (getal % i == 0) { 
      k++;    
     } 
    } 
    return k; 
} 

public boolean determinePrime(long getal) { 
    for (long i = 2; i < getal; i++) { 
     if (getal % i == 0) { 
      return false; 
     } 
    } 
    return true; 
} 

public long determineHighestPrime(long[] deler) { 
    for (int i = deler.length - 1; i > 0; i--) { 
     if (determinePrime(deler[i]) == true) { 
      return deler[i]; 
     } 
    } 
    return 0; 
} 

}

Answer 1

배열을 설정할 때 배열의 크기는 int이어야합니다. 따라서이 : 당신이 long로 매개 변수를 aantalDelers를 선언하기 때문에

delers= new long[aantalDelers]; 

는 컴파일되지 않습니다. 그러나 determineDividers을 호출하면 aantalDelers에 전달한 값은 long이라고 표시된 determineNumberOfDividers의 결과이지만 그 함수는 return k이고 k은 int입니다.

그래서 난 당신이 대신 long의 int을 반환하도록 determineNumberOfDividers을 변경하고 int 대신 long가되도록 aantalDelers 매개 변수를 변경할 수 있다고 생각합니다. 그렇게하면 long 대 -번의 전환을 피할 수 있습니다. 또한 배열 인덱스로 k 및 i을 사용하는 곳에서 long으로 선언 한 경우 int으로 변경해야합니다. 내 머리 위로 떨어져

, 나는 내가 2 개 이상의 ³¹ 약수를 가질 수 2 ⁶³에 수를 생각하지 않기 때문에이 작업을 것이라 생각합니다. 그러나 수학이 잘못되어 배열이 가능하다면 배열 외에 다른 메커니즘이 필요할 것입니다. (사실, 다른 알고리즘을 생각해 내야 할 수도 있습니다.이 알고리즘은 실행하는 데 오랜 시간이 걸릴 것이라는 느낌이 들었습니다.)

Answer 2

변경의 BigInteger에 "거대한"얻을 것이다 모든 변수. Math가 java 피연산자 대신 함수 호출을 사용하도록 업데이트해야하지만 BigInteger에서 모두 사용할 수 있습니다.