백준 4948번: 베르트랑 공준

에라토스테네스의 체를 이용해 소수구하기

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    bool *arr;
    while(true){
        cin >> n;
        if(n == 0)
            break;
        arr = new bool[n * 2 + 1];
        for(int i = 0; i <= n * 2; i++)
        {
            if(i == 0 || i == 1)
                arr[i] = false;
            else
                arr[i] = true;
        }
        for(int i = 2; i <= sqrt(n * 2); i++){
            if(!arr[i])
                continue;
            for(int j = i * i; j <= n * 2; j += i){
                arr[j] = false;
            }
        }
        int result = 0;
        for(int i = n + 1; i <= 2 * n; i++){
            if(arr[i])
                result++;
        }
        cout << result << endl;
        delete [] arr;
    }
}```