BOJ 11653 소인수분해(C++)

소인수분해 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	1786	943	768	55.133%

문제

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

입력

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

출력

N의 인수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

예제 입력 

72

예제 출력 

2
2
2
3
3

예제 입력 2 

3

예제 출력 2 

3

예제 입력 3 

6

예제 출력 3 

2
3

예제 입력 4 

2

예제 출력 4 

2

예제 입력 5 

9991

예제 출력 5 

97
103

힌트

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: wjdclgns12

알고리즘 분류

• 소인수분해

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include    <stdio.h> #include    <cmath> #include    <vector> #pragma warning (disable:4996)   std::vector<int> primes; int main() {     int N;     scanf("%d", &N);           for (int i = 2; i <= sqrt(N); ++i)     {         bool flg = true;         for (int j = 2; j < i; ++j)         {             if (i%j == 0)                 flg = false;         }         if (flg) primes.push_back(i);     }     for (int i = 0; i < primes.size(); ++i)     {         while (N%primes[i] == 0)         {             printf("%d ", primes[i]);             N /= primes[i];         }     }     if (N != 1)         printf("%d", N);     return 0; }

  

이제는 이런게 오히려 어려운 것 같다. 오히려 BFS 다이나믹 같은게 더 쉬운 느낌... 

이 문제는 두 가지로 이루어진다.

1. 입력받은 수 까지의 소수를 찾는다.

2. 소수로 나누어 떨어지지 않을 때 까지 작은 수 부터 나눈다. 

소인수분해라는게 원래 나누어 떨어지지 않을 때 까지(소수로) 나누는 것이므로... 2번은 사실 그것을 그대로 코드화 하였으나 

작은 수 부터 출력하라고 하였으므로 그것을 신경쓴 것 밖에 없다. 

소수 구하는 것은 예전에도 풀었었는데 N까지의 소수를 구할 때 √N * √N = N이므로 한쪽이 더 커지면 한쪽은 무조건 작아져야 한다. 

결국 이보다 큰 소수는 있을 수 없기 때문에 √N까지만 찾아보았다. 

마지막으로 소수로 나누었을 때 1이 나오지 않는다면 큰 소수가 남은 것이므로 출력하였다.