[백준/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 <stdio.h>

int main() {

	int n, k;
	int count = 0;

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++) {
		if (n % i == 0) {
			count++;
		}
		if (count == k) {
			printf("%d", i);
			break;
		}
	}

	if (count != k) {
		printf("0");
	}

	return 0;
}

 

 

 

---

 

 

n과 k를 입력받은 후 for문을 이용해 문제를 해결한다. for문은 최대 n번 돌아갈 수 있다. int i를 1로 설정하여 주어진 값 n을 1부터 시작하여 오름차순으로 약수를 구할 수 있도록 한다. if문의 n % i == 0인 조건을 이용하여 i가 n의 약수인 것을 판별한다. 만약 i가 n의 약수라면 count++를 통해 발견한 약수의 갯수를 증가시킨다. 두 번째 if문은 찾은 약수의 갯수가 찾고자 하는 순서의 약수라면 그 값을 출력하고 반복문을 종료시키도록 한다. 반복문이 종료되고 count가 k값과 동일하다면 그대로 프로그램이 종료되지만, count가 k와 같은 값을 가지지 못하였다면 '0'을 출력하고 프로그램을 종료시킨다.