[Silver V] 2021은 무엇이 특별할까?

[문제 위치]

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

[문제 풀이]

소수 관련 문제이므로 소수 문제에 항상 쓰이는 에라스토스의 체를 이용하여 해결할 수 있다.

 

에라토스테네스의 체는 특정 범위 내의 모든 소수를 효율적으로 구할 수 있는 방법으로, 먼저 2부터 시작하여 해당 수의 배수들을 모두 지우는 방식으로 소수가 아닌 수를 걸러낸다. 이 과정을 반복하면 지정한 범위 내의 소수만 남게 된다.

 

문제에서는 입력값보다 큰 두 개의 연속된 소수의 곱 중 가장 작은 값을 구해야 하므로, 먼저 충분한 범위까지의 소수를 구해두고, 그 소수들을 앞에서부터 차례로 곱해가며 해당 조건을 만족하는 값을 찾는다.

 

입력이 1일 경우 예외적으로 결과가 6이 되며, 이는 2와 3이라는 가장 작은 두 소수의 곱이다. 그 외의 경우는 에라토스테네스의 체로 구한 소수 리스트를 기반으로 조건을 만족하는 소수쌍을 찾으면 된다.

 

아래는 이를 구현한 코드다.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_LIMIT = 10001;
bool isNotPrime[MAX_LIMIT];

void generatePrimes()
{
	for (int i = 2; i <= MAX_LIMIT; i++) {
		if (!isNotPrime[i]) {
			for (int j = i * i; j <= MAX_LIMIT; j += i) {
				isNotPrime[j] = true;
			}
		}
	}
}

int findSmallestPrimeProductExceeding(int input)
{
	if (input == 1) return 6;

	vector<int> primes;
	generatePrimes();
	for (int i = 2; i <= MAX_LIMIT; i++) {
		if (!isNotPrime[i]) {
			primes.push_back(i);
		}
	}
	for (size_t i = 0; i < primes.size() - 1; i++) {
		if (primes[i] * primes[i + 1] > input) {
			return primes[i] * primes[i + 1];
		}
	}
	return -1; // fallback
}

int main()
{
	int input;
	cin >> input;
	cout << findSmallestPrimeProductExceeding(input) << "\n";
	return 0;
}