[알고리즘 문제] 백준 알고리즘 2814번 : 최소인수

생각 및 풀이순서 ↓↓↓

P를 입력받아 P보다 큰 숫자들을 P로 나누어보고 

나누어 떨어지면 계속 P로 나누는걸 반복하는데 만일 나누어떨어지지 않는다면

이보다 큰 숫자로 나눠지지 않을 것이라 판단했다. 

그래서 몫이 1이 될때까지 P로만 나눌 수 있다면 그 숫자가 최소인수가 P인 숫자일 것이라 생각했고 그 숫자들을 배열에 저장했다.

최소인수가 P인 숫자중에서 N번째로 작은 숫자를 출력해야하기 때문에 배열에서 N-1인덱스를 출력해 준다.

 

소스코드↓↓↓

public class primefactor {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        
        //입력받을 숫자 저장 변수
        int N = scan.nextInt();
        int P = scan.nextInt();
        
        //p가 최소인수인 숫자들 저장할 배열
        int[] pf = new int[N];
        
        //소인수분해 할때 쓰일 변수(몫)
        int mok;
        
        if(N < 1 || P > 1000000000) {
            System.out.println("입력이 잘못되었습니다.");
        }else {
            int x = 0;  //배열 인덱스
            
            for(int i=2; i<1000000000; i++) {
                if(i%P != 0) {    //p 나누어떨어지지않으면 다음수로 넘어감
                    continue;
                }else if(i%P == 0) {    //나누어떨어질 경우
                    mok = i/P;    //각각 몫과 나머지를 변수에 저장
                    int namuge = i%P;
                    
                    //숫자가 P와 같을 경우 배열에 추가
                    if(namuge == 0 && mok == 1) {
                        pf[x] = i;
                        x++;
                        continue;
                    }else {
                        while(mok >= P ) {    //몫이 1이 될때까지 계속 소인수분해
                            namuge = mok%P;
                            mok = mok/P;
                            if(namuge != 0 ) {    //P로 나누어 떨어지지 않을 경우 최소인수가 아니기때문에 다음숫자로 넘어감
                                break;
                            }else if(namuge == 0 && mok == 1) {    //계속 P로 나누어 떨어져 몫이 1이 됬을경우 배열에 추가
                                pf[x] = i;
                                x++;
                                break;
                            }
                        }
                    }
                    
                    //N번째 최소인수값을 저장하면 반복문 종료
                    if(x >= N) {
                        break;
                    }
                }
            }
            //N번째 최소인수 값 출력
            System.out.println(pf[N-1]);
        }
 
    }
}
 

결과창

    

간단한 값들을 입력해서 계산해봤는데 대충 맞는 것같지만 혹시 틀린부분이나 빠트린부분이 있다면 댓글로 정답을 아시는분 있다면 알려주세요