[BaekJoon/백준] 11653번

소인수 구하기 문제.

 

나는 무조건 '소수'를 구해서 그 '소수'로 나눠야한다는 생각에 일일이 소수를 구했는데, 다른 분들의 풀이를 보니까

2로 나눠지는건 4로 나눠지는거고, 그게 소수가 아니라는 증거이기도 하니까.. 그냥 숫자를 2부터 하나씩 증가하면서 나눠주는 과정을 가지더라.

 

 

내 풀이

//소수구하기를 응용
//리턴값이 0이면 소수, 1 이상이면 나누어지는 수 중 가장 작은 수 리턴.

#include <stdio.h>

int sosu(int key) {
 
    for(int i = 2; i*i <= key; i++) { // 제곱근까지만 돌면 단축.
        if(!(key%i)) // 나누어 떨어질 경우, 몫을 리턴(0보다 큼)
            return i;
    }
        
    printf("%d\n", key);
    return 0; // 소수인 경우 0을 리턴
    
}

int main() {
    
    int input, p;
    
    scanf("%d", &input);
    
    if(input == 1)
        return 0;
    
    while((p = sosu(input))) {
        input /= p;
        printf("%d\n", p);
    }
    
}

 

다른 분의 풀이. 소수 판별을 고려하지 않았다. 소수의 특성상 나눠질 건 나눠졌어야 하니까.

#include<stdio.h>

int main(void)
{
	int N;
	int i, j;

	scanf("%d", &N);

	for (i = 2; i <= N; i++)
	{
		while (N % i == 0)
		{
			N /= i;
			printf("%d\n",i);
		}
	}
}

 

 

오랜만에 풀이를 다시 시작하니 모자란 부분이 많은 듯 하다. 자리잡아보자..