약수 구하기 > 문제은행

본문 바로가기


실력키우기 수학

1402 : 약수 구하기

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 1908 회    시도횟수: 3175 회   



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

[Copy]
6 3
[Copy]
3


[Copy]
25 4
[Copy]
0


[Copy]
2735 1
[Copy]
1


약수란? 
어떤 수를 나누어 떨어지게 하는 수를 어떤 수의 약수라 한다.
즉 a * b = c일 경우 a와 b는 c의 약수가 된다.
1은 모든 수의 약수이며 자기 자신 또한 약수가 된다.

배수란?
어떤 수의 1배, 2배, 3배, 4배... 한 수를 어떤 수의 배수라 한다.
 즉 a * b = c 일 경우 c는 a와 b의 배수가 된다.
 자기 자신도 배수이며 배수의 개수는 무한하다.

프로그램에서 약수와 배수를 확인하기 위해서는 나머지 연산을 이용하면 된다.
 a % b 가 0이면 a는 b의 배수이고, b는 a의 약수가 된다.

코드
01    for (i = 1; i <= N; i++) {
 02        if (N % i == 0) {                      // i가 N의 약수이면
 03            cnt++;                            // 약수의 개수(cnt)를 증가한다.
 04            if (cnt == K) {                    // 약수의 개수가 K개이면
 05                printf("%d\n", i);              // K번째 약수인 i를 출력하고  
 06                return 0;                     // 프로그램을 종료한다.
 07            }
 08        }
 09    }

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





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.