[c++] 백준 2312 - 수 복원하기(소인수분해, 소수, 에라토스테네스의 체)

0. [c++] 백준  -

https://www.acmicpc.net/problem/2312

1. 풀이

1) 에라토스테네스의 체를 활용하여 소수를 우선적으로 구한다.

2) 구한 소수를 바탕으로 입력으로 주어진 수에 소인수분해를 시행한다.

3) 그 결과를 출력한다.

2. 소스코드

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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

#include<iostream> #include<vector> #include<cstring>   using namespace std;   bool eratosthenes_sieve[100002]; vector<int> prime;     void primeFactorization(const int& N) {     //기저 사례 : 이미 소수인 경우 출력을 하고 종료한다.     if (eratosthenes_sieve[N]) {         cout << N << " 1\n";         return;     }          int copy_N = N;     //찾은 소수를 바탕으로 소인수분해를 실시한다.     //불필요한 연산을 줄일 수 있다.     for (int i = 0; i < prime.size(); i++) {         //기저 사례 : 자기자신이 소수가 된 경우라면, 출력하고 종료.         if (eratosthenes_sieve[copy_N]) {             if (copy_N == 1)                 return;             cout << copy_N << " 1\n";             return;         }           //prime[i]가 자신의 인수에 속한다면, 몇번이나 곱해졌는지 확인한다.         if (copy_N % prime[i] == 0) {             int count = 0;             while (copy_N % prime[i] == 0) {                 count++;                 copy_N /= prime[i];             }             cout << prime[i] << " " << count << "\n";         }     } }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int N, origin;     cin >> N;     //계산을 시작하기 전에 100000범위내의 소수를 미리 탐색한다.     memset(eratosthenes_sieve, true, sizeof(eratosthenes_sieve));     for (int i = 2;i <= 100000;i++) {         if (i*i > 100000)             break;         if (eratosthenes_sieve[i]) {             for (int j = i + i;j <= 100000;j += i)                 eratosthenes_sieve[j] = false;         }     }     //eratosthenes_sieve를 활용해 찾은 소수를 활용하기 편하게 vector<int>에 저장한다.     for (int i = 2; i <= 100000; i++) {         if (eratosthenes_sieve[i])              prime.push_back(i);     }          //소인수분해를 시행하자.     for (int i = 0; i < N; i++) {         cin >> origin;         primeFactorization(origin);     }         return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!