[백준 2501] 약수 구하기

• 안녕하세요. BlockDMask 입니다.

• 오늘도 간단하게 전체 탐색법을 이용하여 약수를 구하는 문제를 풀어보았습니다.

0. 제목

• 백준 2501 약수 구하기

• BOJ 2501 약수 구하기

1. 문제 설명

약수란

어떤 자연수 a, b 가 있을때

a를 b로 나누었을때 나머지가 0 이면 b는 a의 약수라 한다.

12 를 예로 들자면

12 / 1 = 12 ---> 0

12 / 2 = 6 ---> 0

12 / 3 = 4 ---> 0

12 / 4 = 3 ---> 0

12 / 5 = 2 ---> 2

12 / 6 = 2 ---> 0

12 / 7 = 1 ---> 5

12 / 8 = 1 ---> 4

12 / 9 = 1 ---> 3

12 / 10 = 1 ---> 2

12 / 11 = 1 ---> 1

12 / 12 = 1 ---> 0

12 의 약수는 1, 2, 3, 4, 6, 12 입니다.

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

-- 입력 -- 

N (1<= n <= 10,000)

K (1<= k <=n)

-- 출력 --

n 의 약수들 중 k번째로 작은 수를 출력합니다.

만일 n의 약수의 개수가 k개 보다 적어서 k번째 약수가 존재하지 않을 경우에는 0을 출력합니다.

2. 풀이 과정

-> n, k 를 받는다.

-> 1부터 시작하여 n까지 n의 약수를 구한다.

-> 약수를 하나 구할때마다 k 값을 하나씩 뺀다.

-> k값이 0이 되면 k 번째 약수를 구한 것이 되므로 return 후 출력.

-> k 번째 약수를 구하지 못하면 return 0;

3. 소스 코드

//https://www.acmicpc.net/problem/2501
//BOJ_2501_약수 구하기
 
#include<iostream>
#include<cstdio>
using namespace std;
 
int Solution(int n, int k){
 
    for(int i=1; i<=n; i++){
        if(n%i ==0){
            k--;        //약수 발견시 하나씩 감소
            if(k==0) return i;
        }
    }
 
    return 0;
}
 
int main(void){
    int n;
    int k;
 
    cin >> n >> k;
    printf("%d", Solution(n,k));
 
    return 0;
}

4. 인증

문제출처 - https://www.acmicpc.net/problem/2501

감사합니다.