Baekjoon-11653

접근 

 자연수 N을 소인수분해 직접 할 때, 2인 작은 수부터 나누어서 나누어 떨어지는 값을 찾는다. 나누어 떨어진 값으로 나누고 그 값을 다시 2인 작은 수부터 나눈다. 더이상 나눌 수 없는 값이 나올때까지 반복한다.

 => 풀이 과정을 보면 수학 공식을 이용해서 찾을 수가 없을 것 같다.

 

#include <stdio.h>

int main() {
    int num;
    int count;
    int tmp;

    scanf("%d", &num);
    tmp = num;

    if(num == 1) return 0;


    while(tmp !=1) {
        for(int i=2;i<=num;i++) {
            if(tmp%i == 0) {
                printf("%d\n", i);
                tmp = tmp / i;
                break;
            }
        }
    }

    
}

결과

다른 사람들의 결과를 찾아보면 시간이 더 빠른게 있는지 확인해본다. 

=> 찾아보니 나보다 시간이 훨씬 좋은 결과지가 있다(메모리 같거나 적고, 시간이 더 빠른것)... 분석해보자....

 

방법 1) 제곱을 이용해서 비교 횟수를 줄인다.

방법 2) 제곱근까지만 비교한다.

 

크게 이 두가지 방법을 쓰면서 시간을 줄인다.