백준 24309번: 2021은 무엇이 특별할까? (C++)

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

24039번: 2021은 무엇이 특별할까?

---

Solved By: Primality Test

 

n의 최댓값이 10000이므로 10000까지의 소수를 모두 구해줍니다. 연속한 소수들을 2개 골라 곱해보면서 주어진 n보다 값이 커지면 그 값을 답으로 출력하도록 합니다.

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 10001
using namespace std;

vector<int> prime;
bool check[MAX];
int n;

void makePrime(){
    for(int i = 2; i < MAX; i++){
        if(check[i]) continue;
        for(int j = i * 2; j < MAX; j += i) check[j] = true;
    }
    
    for(int i = 2; i < MAX; i++){
        if(!check[i]) prime.push_back(i);
    }
}

int main(){
    cin >> n;
    makePrime();
    int ans;
    for(int i = 0; i < prime.size() - 1; i++){
        int value = prime[i] * prime[i + 1];
        if(value > n){
            ans = value;
            break;
        }
    }
    
    cout << ans;
    return 0;
}