백준 - 2501번 약수구하기(수학)

문제

어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.

6을 예로 들면

• 6 ÷ 1 = 6 … 0
• 6 ÷ 2 = 3 … 0
• 6 ÷ 3 = 2 … 0
• 6 ÷ 4 = 1 … 2
• 6 ÷ 5 = 1 … 1
• 6 ÷ 6 = 1 … 0
  그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.

출력

첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다. 만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.

C++ 풀이

직관적으로 약수가 될 수 있는 변수 i를 하나씩 늘려가면서 약수 인 경우 그 개수 변수에 해당하는 n을 하나씩 증가시키면서 K의 도달 여부나, K까지 도달 못한 경우 예외처리를 통해 풀이하였다.

#include <iostream>

using namespace std;

int main()
{
    int N,K,i=0,n=0;
    cin >> N >> K;
    
    while(1){
        i++;
        if (!(N%i)) // 약수 늘리는 로직
            n++;
        if (n==K){ // K번째 약수인 경우 i 를 출력
            cout << i;
            return 0;
        }
        if (i==N){ // N의 약수의 개수가 K보다 작아서 i가 N까지 도달한 경우
            cout << 0;
            return 0;
        }
    }


    return 0;
}

C++ 숏코딩 풀이

#import<iostream>
int N,K,i,j;main(){for(std::cin>>N>>K;i<N&&j<K;j+=N%++i?0:1);printf("%d",K>j?0:i);}

가독성 버전

#import<iostream>
int N,K,i,j; // 전역변수로 설정하여 i, j = 0으로 자동 초기화
main(){
	for(std::cin>>N>>K;i<N&&j<K;j+=N%++i?0:1);
    // N, K를 입력 받고
    // for loop의 탈출 조건은 i가 N을 넘지 않으면서(&&) j 도 K를 넘지 않아야 됨.
    // j += N % ++i ? 0:1 는 삼항연산자를 이용하여
    // ++i가 N의 약수인 경우 j +=1, 아닌 경우 그대로
    // for loop를 끝까지 순회하였을 때 결국 j는 K가 되거나 혹은 i가 1씩 증가하여 끝까지 가거나이다.
    
    printf("%d",K>j?0:i);
    // 역시 삼항연산자를 이용하여 K가 j보다 큰 경우, 
    // 즉 K가 커서 i가 N이 되버린 경우 0을 출력하고 아니면 i를 출력한다.
 }