[BaeKJoon/C] 백준2501 c 약수 구하기

https://www.acmicpc.net/problem/2501

2501번: 약수 구하기

 

문제

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

 

코드

#include <stdio.h>
 
int main() {
 
    int n, k;
    int cnt = 0;
    int i;
    scanf("%d %d", &n, &k);
    
 
    for (i = 1; i <= n; i++) {
        if (n % i == 0)
            cnt++;
        if (cnt == k)
            break;
    }
    if (i <= n) printf("%d", i);
    else printf("0");
 
    
}

풀이

if (n % i == 0)

            cnt++;

        if (cnt == k)

            break; 

ex) n=16  k=4

i    =1 2 4 8 16

cnt =1 2 3 4 5

k==cnt이면 

cnt 4 = i 8과 같다

 

입력 16 4

출력 8