[C++] 백준 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을 출력하시오.

접근

처음엔 약수를 구해서 그 약수들을 큐에 넣고 구하는 방법으로 구현했다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <queue>
using namespace std;

queue <int> pq;

int main() {

    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            pq.push(i);
        }
    }
   
    for (int i = 1; i < k; i++) {
        if (pq.size() < k) {
            printf("0");
        }
        pq.pop();
    }

    printf("%d", pq.front());
    return 0;
}

첫번째 경우인 6의 약수들 중에서 3번째로 작은수는 출력이 되었으나 25의 약수중 4번째로 작은 수에서 오류가 나서 틀린답이되었다

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
using namespace std;

int main() {

    int n, k;
    int cnt = 0;
    int ans = 0;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            cnt++;
            if (cnt == k) {
                ans = i;
                break;
            } 
        }
    }
    printf("%d", ans);
  
    return 0;
}

리뷰

큐를 사용하지 않고 나머지가 0이되는경우마다(약수일때) cnt를 증가시킨다 증가시키면서 cnt와 k가 똑같아 지는 때가 k번째로 작은수가 되니까 이렇게 구했다

학습

바로 쉽게 구할 수 잇는데 이 방법을 생각못했다 ㅋ ㅠ

출처

2501번: 약수 구하기 (acmicpc.net)

2501번: 약수 구하기