문제

문제 링크

어떻게 접근할 것인가?

  • 처음에는 소수를 다 찾아주고 그 소수들을 나눠가면서 값을 찾으려고 했다.(하지만 이건 투머치다.)
  • 결국 선택한 방법은 나눌 수 있는 수를 순서대로 찾으면서 나머지가 남을 때까지 값을 계속 쪼개주는 식으로 나름 효율적인 알고리즘을 만들었다ㅎㅎ

코드

#include <cstdio>

using namespace std;

int main(){
    int n, input;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &input);
        while(input != 1){
            for(int i = 2; i <= input; i++){
                int count = 0;
                while(input % i == 0){
                    input /= i;
                    count++;
                }
                if(count != 0)printf("%d %d\n", i, count);
            }
        }
    }
}

느낀점

  • 괜히 체를 쓰면 좋다는 얘기를 듣고 체를 써볼라고 하다가 오히려 망할뻔
  • 그냥 틀을 벗어나서 내가 효율적이라고 생각하는 식으로 코드를 짜보자!