백준 9753 _ 짝 곱

www.acmicpc.net/problem/9753

9753번: 짝 곱

---

✨ 내 소스 코드

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int vec[50002];
	vector<int> v;
	for (int i = 0; i <= 50001; i++) {
		vec[i] = i; 
	}

	//소수 구하기 _ 에라토스테네스의 체
	for (int i = 2; i <= 50001; i++) { 
		if (vec[i] == 0) { 
			continue; 
		} 
		else {
			v.push_back(vec[i]);
		}
		for (int j = 2; j*vec[i] <= 50001; j++) {
			vec[j*vec[i]] = 0; 
		} 
	}
	
	vector<int> mul;

	//소수들의 곱 저장
	for (int i = 0; i < v.size(); i++) {
		for (int j = i + 1; j < v.size(); j++) {
			mul.push_back(v[i] * v[j]);
		}
	}
	
    //저장한 소수의 곱을 정렬
	sort(mul.begin(), mul.end());

	int T;
	cin >> T;
	while (T--) {
		int K;
		cin >> K;
		int answer;
	
    	//이분탐색으로 원하는 값 찾기
		int low = 0, high = mul.size() - 1;

		while (low <= high) {
			int mid = (low + high) / 2;
			if (mul[mid] >= K) {
				answer = mid;
				high = mid - 1;
			}
			else
				low = mid + 1;
		}
		cout << mul[answer]<<'\n';

	}

	return 0;
}

 

🙏 문제 풀이

정수 K (1 ≤ K ≤ 100,000)보다 크거나 같은 서로 다른 소수의 곱을 구하는 문제이기 때문에

50,001까지의 소수만 구하면 2와 곱해질 경우, 100,000보다 커질 것이라고 생각하였다

 

50,001 까지의 소수를 구해서 저장을 해놓고

소수들의 곱을 저장하여 이분탐색을 통해 K보다 크거나 같은 소수를 구하였다

 

⭐ 문제 풀이 결과