[java] 소인수 분해 코드 구현 방법

소인수분해 : 어떤 수를 소수들의 곱으로 표현하는 것

 

예시) 20 = 2 * 2 * 5

 

여기서, 소인수는 2, 5

 

◎ 소인수의 표현 방법 구상

1. 지정한 변수(n)를 1보다 클때까지 반복문 설정
 → n을 소인수로 나눈 후 그 값을 n에 다시 저장할 것
2. 소수는 2부터 시작하기 때문에 초기값 설정
 → 소수 : 1과 자기자신만을 갖는 수
3. n을 소인수로 나눈 후 n에 다시 저장하고 다시 2부터 시작해 소인수를 찾음

while(n > 1){
    int i = 2;
    while(true){
        if(n % i == 0) {
            n /= i;
            break;
        }
        i++;
    }
}​

 

여기서 배열, 리스트, Set 등으로 저장하면 되고 중복되는 값은 이후 필터링을 하거나 저장하지 않으면 됨.