[백준 2501] 약수 구하기

문제 (Bronze 3)

어떤 자연수 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을 출력하시오.

문제 풀이

문제의 해결 과정 자체는 간단합니다.

1. N, K를 입력 받는다.
2. N의 약수를 구한다.
3. N의 약수의 개수가 K보다 작다면 0을, 크거나 같다면 K번째로 큰 약수를 출력한다.

이 문제에서는 1~N까지 반복문을 돌면서 약수를 구해도 시간초과가 나지 않지만 다른 문제들을 위해 효율적으로 약수를 구하는 법을 익혀둡시다!😀

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> v;
    for(int i=1; i*i<=N; ++i) {
        if(N % i == 0) {
            
            v.push_back(i);
            if(i * i != N) v.push_back(N / i);
        }
    }
    
    if(v.size() < K) cout << 0 << endl;
    else {
        sort(v.begin(), v.end());
        cout << v[K-1] << endl;
    }
    
    return 0;
}

문제 링크

2501번: 약수구하기