[ 백준 4948 ] 베르트랑 공준 (C++)

백준의 베르트랑 공준(4948) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는, 입력으로 주어지는 범위 내에서 소수가 몇개인지 찾아야 하는 문제이다. 본인은, 입력을 받기 전에

   SoSoo[] 라는 bool 형 1차원배열을 만들어서 소수가 아닌 숫자들을 모두 false로 체크해주었다.

   즉, SoSoo[a] = false 의 의미는, "a는 소수가 아니기 때문에 답이 될 수 없습니다." 를 의미한다.

   소수가 아닌 숫자들을 찾는 방법은 어렵지 않다.

   N의 최대값이 123456 이기 때문에, 2N의 최대값은 246912이 될 것이다. 즉, 2부터 246912까지 각 숫자들의 배수들을 모두

   false로 체크해주면 된다.

  

   위와 같이 구현을 하게 되면, 모든 2~ 246912 범위 내에 있는 모든 소수가 아닌 숫자들을 false로, 소수들은 true로 설정될 것이다.

  

   이후 과정은 어렵지 않다. N + 1 ~ 2N 까지 반복하면서 SoSoo배열의 값이 true라면 Count해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 246913
using namespace std;
 
int N;
bool SoSoo[MAX];
 
void Input()
{
    cin >> N;
    if (N == 0) exit(0);
}
 
void Solution()
{
    int Cnt = 0;
    for (int i = N + 1; i <= 2 * N; i++)
    {
        if (SoSoo[i] == true) Cnt++;
    }
    cout << Cnt << endl;
}
 
void Eratos()
{
    memset(SoSoo, true, sizeof(SoSoo));
    SoSoo[0] = SoSoo[1] = false;
    for (int i = 2; i < MAX; i++)
    {
        for(int j = 2; j *i < MAX; j++)
        {
            SoSoo[i*j] = false;
        }
    }
}
 
void Solve()
{
    Eratos();
    while (1)
    {
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}