백준9753 - 짝 곱

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

9753번: 짝 곱

에라토스테네스의 체와 이분 탐색을 이용하여 해결한 문제이다. K가 10만으로 주어졌을 때 100001을 출력하기 때문에 50001까지의 소수를 모두 구한다. 그런 다음 구한 소수를 서로 곱하여 벡터에 저장하여 정렬한다. 정렬된 벡터에서 K보다 크거나 같은 수 중 최소의 값을 구한다. 답을 찾는 과정은 이분탐색으로 구현한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50002
using namespace std;

int T, K;
int mat[MAX];
vector<int> v;
vector<int> l;

//에라토스테네스의 체
void func() {
    for(int i = 1; i < MAX; i++) {
        mat[i] = i;
    }
    for(int i = 2; i < MAX; i++) {
        if(!mat[i]) {
            continue;
        }
        else {
            v.push_back(i);
        }
        for(int j = i + i; j < MAX; j += i) {
            mat[j] = 0;
        }
    }
}

int main() {
    func();
    
    //구한 소수를 서로 곱하는 과정
    for(int i = 0; i < v.size() - 1; i++) {
        for(int j = i + 1; j < v.size(); j++) {
            if(i != j) {
                l.push_back(v[i] * v[j]);
            }
        }
    }
    
    //오름차순 정렬
    sort(l.begin(), l.end());
    
    cin >> T;
    while(T--) {
        cin >> K;
        int ans = 0;
        int left = 0, right = l.size() - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(l[mid] >= K) { //현재 찾은 값이 K이상이면 답으로 현재 위치를 갱신하고 범위를 작은 쪽으로 줄인다.
                ans = mid;
                right = mid - 1;
            }
            else { //현재 찾은 값이 K보다 작으면 범위를 큰 쪽으로 줄인다.
                left = mid + 1;
            }
        }
        cout << l[ans] << '\n';
    }

    return 0;
}