KOI 본선 2008 초1- 약수 구하기 > 문제은행 : 정보올림피아드&알고리즘



1402 : 약수 구하기

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
329 회   
시도횟수
528 회   

문제

어떤 자연수 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을 출력하시오.

입력 예

6 3

출력 예

3

입력 예

25 4

출력 예

0

입력 예

2735 1

출력 예

1

Hint!

약수란? 어떤 수를 나누어 떨어지게 하는 수를 어떤 수의 약수라 한다. 

즉, a * b = c일 경우 a와 b는 c의 약수가 된다. 

1은 모든 수의 약수이며 자기 자신 또한 약수가 된다. 


배수란? 어떤 수의 1배, 2배, 3배, 4배... 한 수를 어떤 수의 배수라 한다. 

즉, a * b = c 일 경우 c는 a와 b의 배수가 된다. 

자기 자신도 배수이며 배수의 개수는 무한하다. 

프로그램에서 약수와 배수를 확인하기 위해서는 나머지 연산을 이용하면 된다. 

a % b 가 0이면 a는 b의 배수이고, b는 a의 약수가 된다. 


코드 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
for (i = 1; i <= N; i++)
{
    if (N % i == 0)   // i가 N의 약수이면
    {
        cnt++// 약수의 개수(cnt)를 증가한다.
        if (cnt == K)   // 약수의 개수가 K개이면
        {
            printf("%d\n", i); // K번째 약수인 i를 출력하고
            return 0// 프로그램을 종료한다.
        }
    }
}
 
cs

 


코드분석 

1부터 차례대로 N의 약수인지 확인하여 약수이면 cnt를 증가해 나가다가 cnt가 K와 같아지면 i를 출력하고 프로그램을 종료하도록 작성된 프로그램이다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP