정올 C - 1402번 수학1 - 약수 구하기

문제 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=678&sca=2030

JUNGOL

문제

어떤 자연수 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번째로 작은 수를 출력하는 프로그램을 작성하시오.

 

 

 

[그림1] 입 출력 형식

[그림2] 입 출력 예제

 

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; // 프로그램을 종료한다.         }     } }   Colored by Color Scripter

cs

 

 

코드분석 

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

 

정답 : 

# include <stdio.h>

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