[C++백준] 실버 3/ 2312번 수 복원하기

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

2312번: 수 복원하기

 

 

#include <iostream>
#include<string>
#include<math.h>
#include<istream>
#include<vector>
#include<algorithm>
using namespace std;
 
bool prime[100010];
 
long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}
 
 
int main() {
 
    
    prime[0] = prime[1] = true;
 
    for (int i = 2; i < 100001; i++) {
        if (!prime[i]) {
            for (int j = 2; j*i < 100001; j++) {
                prime[j*i] = true;
            }
        }
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        vector<int>v(num+1);
        while (num != 1) {
            for (int j = 2; j <=num; j++) {
                if (!prime[j]) {
                    
                    
                    int ans=gcd(num, j);
                    
                    if (ans > 1) {
                        v[ans]++;
                        num /= ans;
                        
                        
                        
                    }
                    
                }
            }
        }
 
        for (int j = 2; j <v.size(); j++) {
            if (v[j] != 0) {
                cout << j << " " << v[j] << endl;
            }
        }
 
        
 
 
    }
 
    
 
 
}

에라토스테네스의 체로 소수를 판별하고, 최대공약수를 찾아주는 gcd 메서드를 만들면 문제를 풀 수 있다.

참고로 vector만들때 n+1로 크기 지정을 해줘야한다. n으로 해주니 틀렸습니다가 떴다.

왜냐면 7이 n으로 들어왔을때 벡터 크기를 8이 아니라 7로만 해준다면 0부터 6까지만 돌기 때문에 7의 약수인 7까지 순회하지 않기 때문이다.