<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 2501] 약수 구하기

BlockDMask 2017. 10. 17. 13:57
반응형
  • 안녕하세요. 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. 소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//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==0return i;
        }
    }
 
    return 0;
}
 
int main(void){
    int n;
    int k;
 
    cin >> n >> k;
    printf("%d", Solution(n,k));
 
    return 0;
}
cs


4. 인증


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

감사합니다.

반응형