백준 24039번 2021은 무엇이 특별할까? c++ 풀이

문제

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

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

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

입력

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

출력

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

제한

•  1≤�≤10000$1 \le N \le 10\,000$ 
•  �$N$은 정수이다.

예제 입력 1 복사

2020

예제 출력 1 복사

2021

예제 입력 2 복사

2021

예제 출력 2 복사

2491

 

 

에라토스테네스의 체로 간단하게 풀이할 수 있었다.

 

주의할 점

1은 소수가 아니다.

에라토스테네스의 체 for문을 만들 때  j = i * i 를 해 줘야 한다.

 

- c++ 풀이

#include <bits/stdc++.h>

using namespace std;

int n;

bool arr[10001] = {false,};

vector<int> primes;

void prime() {


    for (int i = 2; i < 10001; i++) {
        for (int j = i * i; j < 10001; j += i) {
            arr[j] = true;
        }
    }

    for (int i = 2; i < 10001; i++) {
        if (arr[i] == false) {
            primes.push_back(i);
        }
    }


}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    prime();


    for (int i = 0; i < primes.size(); i ++) {

        if (primes[i] * primes[i + 1] > n) {
            cout << primes[i] * primes[i + 1];
            return 0;
        }

    }


    return 0;
}