[백준] 4948번 베르트랑 공준

문제: 4948번: 베르트랑 공준

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

bool state[(123456 * 2) + 1];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(state, state + (123456 * 2) + 1, true);
    for (int i = 2; i <= (123456 * 2) + 1; i++) {
        if (!state[i]) continue;
        for (int j = 2 * i; j <= (123456 * 2) + 1; j += i) {
            state[j] = false;
        }
    }

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        int cnt = 0;
        for (int i = n + 1; i <= 2 * n; i++) {
            if (state[i])
                cnt++;
        }
        cout << cnt << "\n";
    }

    return 0;
}

 

그냥 에라토스테네스의 체 개념을 알고 있으면 해결할 수 있는 문제이다. 

 

일단 n 의 범위가 1부터 123456까지이다. n 보다 크고 2n 보다 작거나 같은 수 에서 소수를 찾아야 하는 문제이므로 state 의 범위를 (123456 * 2) + 1 로 설정해줬다.

 

for 문을 돌면서 소수들만 남기도록 했다. 그리고 while 문을 돌면서 n 값을 입력받고 그 값을 이용해서 for 문을 돌려 state 가 true 인 것만 cnt 에 반영하도록 했다. state 가 true 라는 것은 소수라는 의미니까..

 

for 문 다 돌고 cnt 출력해주면 끝 !_!