[Algorithm] 입력받은 수를 소인수 분해하기

정수를 입력받아 소인수를 구해 출력하기

어떤 수를 소인수 분해하려면 입력받은 수를 2부터 차례대로 입력받은 수(NUM)의 제곱근까지의 숫자로 나누어 떨어지는지를 계산하시면 됩니다. 제곱근까지의 수 중 입력받은 수(NUM)을 처음으로 나누어 떨어지게 하는 수가 있으면 그 수는 소수이고, 입력받은 수(NUM)는 소인수가 됩니다. 소인수를 구했으면, 그때의 몫을 입력받은 수(NUM)에다가 치환하고 다시 NUM의 제곱근까지의 숫자로 나누는 작업을 반복합니다. 만약 제수가 NUM의 제곱근보다 커지면 그떄는 몫인 NUM자체가 그 수의 소인수가 됩니다.

 

C언어 / C++ 코드

#include<stdio.h>
#include<math.h>

main()
{
	int num,b,c,d,mok,nmg;
	int a[100];
	
	scanf("%d",&num);
	b=-1;
	
	while(1){
		c=2;
		d=(int)sqrt(num);
		
		while(1){
			if(c>d){
				if(c>d){
					c = num;
					break;
				}
			}
			mok = num / c;
			nmg = num-mok*c;
			
			if(nmg ==0){
				break;
			}else{
				c++;
			}
		}
		b++;
		a[b] = c;
		if(num==c){
			break;
		}
		num = mok;
	}
	
	for(int i=0;i<=b;i++){
		printf("[%d]",a[i]);
	}
}