[백준] 24039

2021은 무엇이 특별할까?

문제

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

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

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

입력

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

출력

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

풀이

#include <iostream>
#include <vector>

bool arr[10001];
std::vector<int> v;

int main(void) {
    int n;
    std::cin >> n;

    for (int i = 2; i < n; i++) {
        if (arr[i]) continue; // 이미 체크가 되어있으면 건너뛰기
        for (int j = 2 * i; j <= n; j += i) { // i * 2 부터 i * n까지 거르기
            arr[j] = true;
        }
    }

    for (int i = 2; i < n; i++) {
        if (!arr[i]) v.push_back(i);
    }

    int len = v.size();

    for (int i = 0; i + 1 < len; i++) {
        if (v[i] * v[i + 1] > n) {
            std::cout << v[i] * v[i + 1];
            break;
        }
    }

    if (n < 4) {
        std::cout << 6;
    }
}

반성회

1. 에라토스테네스의 체를 이용하여 배열에서 소수 인덱스를 쭉 구한다
2. 이렇게 구한 소수들을 벡터에 밀어넣어서 연속되게 만든다
3. 연속된 소수들끼리 브루트포스로 하나씩 곱해서 n을 처음으로 넘는 값을 구한다