[C/C++] 백준 11653 C언어

백준 11653번

 

정수 N이 주어졌을 때, 소인수 분해하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

 

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

#include <stdio.h>

int main()
{
        int N=0,P=2;
        scanf("%d", &N);
        for(int i=0; N>1; i++){
                if(N%P==0) {N/=P; printf("%d\n", P);}
                else{P++;}
        }

}

 

[23-04-09 수정]

이 글을 생각보다 많은 분들이 보고 계신 것 같아 이전 설명을 지우고 다시 작성해보려 합니다.

 

문제에서 요구하는 답이 소인수(Primefactor)이므로 위와 같이 루프를 이용하여 간단히 해결할 수 있습니다.

입력값이 천 만이기 때문에 시간 초과는 발생하지 않습니다.

 

위 풀이를 재귀 함수로 변환하면 다음과 같습니다.

 

#include <stdio.h>

int PrimeFactor(int a){
        int i=2;
        if(a==1){return NULL;}
        while(a%i!=0){i++;}
        printf("%d\n", i);
        PrimeFactor(a/i);
}

int main()
{
	int a;
	scanf("%d", &a);
        PrimeFactor(a);
        return 0;
}

 

소인수분해 문제는 4149번 문제가 특히 어려운데 이와 관련된 내용은 폴라드 포 알고리즘을 공부해보시면 좋을 것 같습니다.