알고리즘(C++) / 백준 2501 : 약수 구하기

2501 - 약수 구하기

www.acmicpc.net/problem/2501

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을 출력하시오.

 

코드

//2501 약수 구하기
#include <iostream>
using namespace std;

int main() {
	int N, K = 0; //N,K는 자연수
	cin >> N >> K;
	//0 < N <= 10000, 0 < K <=N 

	int divisor[10000] = { 0, }; //약수를 저장하는 배열 0으로 초기화

	int num = 0; //약수의 개수
	for (int i = 1; i <= N; i++) {
		if (N % i == 0) {
			divisor[num] = i; //약수 저장
			num++;
		}
	}

	if (num < K) { //K번째 약수가 존재하지 않을 경우
		cout << "0" << endl;
	}
	else
		cout << divisor[K-1] << endl;
        
	return 0;
}

 

출력

 

설명

N, K는 자연수이다. divisor이라는 배열을 0으로 초기화하여 만든다. divisor 배열은 N이 10000을 초과하지 않으므로 약수의 개수가 10000개가 넘을수가 없다.

약수의 개수를 나타내는 num변수와 K변수를 비교하여 K가 num보다 크다면 약수가 존재하지 않는 것을 의미하므로 0을 출력한다. K가 num보다 작거나 같다면 K번째로 작은 수를 출력한다. 이때 배열은 0부터 저장되기 때문에 K-1번째 배열을 출력한다.

 

고찰

처음 제출했을 때 단지 오타로 인하여 컴파일 에러가 발생했다.