[BOJ/Silver 5] 백준 24039 2021은 무엇이 특별할까?(C++)

문제 링크

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

 

문제

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 주어진 수 N이 주어진다.

 

출력

첫 번째 줄에 N보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

 

제한

•  1 ≤ N ≤ 10,000
•  N은 정수이다.

 

예제 입력 1

2020

예제 출력 1

2021

예제 입력 2

2021

예제 출력 2

2491

 

알고리즘 분류

• 소수 판정

 

풀이

에라토스테네스의 체로 소수들을 기록한다.

첫 번째 소수부터 연속된 소수를 곱하면서, N보다 큰 특별한 수가 나오면 해당 수를 정답으로 판정한다.

최대로 등장할 수 있는 특별한 수는 101과 103을 곱한 10,403이다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 12345
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int DP[MAX];
vector<int> Primes;
bool Specials[MAX];
int Answer;

void init() {
	for (int i = 0; i < MAX; i++) {
		DP[i] = i;
	}
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (DP[i] == 0) continue;
		for (int j = (i * i); j < MAX; j += i) {
			DP[j] = 0;
		}
		Primes.push_back(i);
	}
}

void input() {
	cin >> N;
}

void settings() {
	for (int i = 1; i < (int)Primes.size(); i++) {
		int Prime = Primes[i - 1] * Primes[i];
		if (N < Prime) {
			Answer = Prime;
			return;
		}
	}
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO

	init();
	input();
	settings();
	printAnswer();

	return 0;
}