[BaekJoon/C] No.2312 : 수 복원하기

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

 

 

소스코드 & 문제풀이

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

//숫자 n의 소인수 분해를 출력하는 시그마함수를 만들어줍니다
void sigma(int n)
{
    //짝수 소인수
    if (n % 2 == 0) 
    {
        int c = 0; //2로 나눌 수 있는 횟수를 세는 변수를 선언합니다
        while (n % 2 == 0) 
        {
            c++; //나눌 때마다 카운트를 증가합니다
            n /= 2; //n을 2로 나누며
        }
        printf("2 %d\n", c); //소인수 2와 그 지수를 출력합니다
    }

    //홀수 소인수
    for (int p = 3; p * p <= n; p += 2) //3부터 시작하여 홀수만 검사합니다
    {
        if (n % p == 0) //n이 p로 나누어떨어지는 경우로
        {
            int c = 0; //p로 나눌 수 있는 횟수 세는 변수를 선언합니다
            while (n % p == 0) 
            {
                c++; 
                n /= p; 
            }
            printf("%d %d\n", p, c); //마찬가지로 소인수 p와 그 지수를 출력합니다
        }
    }

    //반복문 이후 n이 1보다 크면, 남은 n은 소수이므로 n과 1을 출력합니다
    if (n > 1)
        printf("%d 1\n", n);
}

int main()
{
    int t, n; //테스트 개수로 사용할 t와, 소인수분해할 숫자인 n을 선언합니다
    scanf("%d", &t); 
    while (t--) //t번 반복하며
    {
        scanf("%d", &n); //각 테스트에서 숫자 n 입력받고
        sigma(n); //입력받은 숫자 n을 소인수분해합니다
    }
    return 0;
}

 

 

예제 입출력 결과