[알고리즘] 백준 4948번 "베르트랑 공준" (C/C++) - Don 임베디드

문제요약:

 

베르트랑 공준은 임의의 자연수 N에 대하여,

N보다 크면서 2N보다 작거나 같은 소수는 적어도 하나 존재한다는 내용이다.

예를 들어, 10보다 크고 20보다 작거나 같은 소수는 4개 존재한다.

(11, 13, 17, 19)

그리고, 14보다 크고 28보다 작거나 같은 소수는 3개 존재한다.

(17, 19, 23)

자연수 N이 주어졌을 때,

N보다 크고 2N보다 작거나 같은 소수의 개수를 고하는 프로그램을 작성하라.

 

 

제약:

 

시간제한 1초, 메모리 256MB

1<= N <=123456

 

 

입력:

 

입력은 여러 개의 N이 순서대로 주어진다.

N으로 0이 입력되면, 프로그램을 종료한다.

 

예제 1 입력.	예제 1 출력.
1 10 13 100 1000 10000 100000 0	1 4 3 21 135 1033 8392

 

 

정답코드:

 

#include <iostream>
 
using namespace std;
 
#define MAX_N_VALUE  (123456)
#define MAX_2N_VALUE (2 * MAX_N_VALUE)
 
// boolean array to store if a number is prime or not.
bool abIsPrime[MAX_2N_VALUE + 1];
 
void checkPrime()        // Sieve of Eratosthenes.
{
    // initialize bIsPrime.
    for (int i = 1; i <= MAX_2N_VALUE; i++)
    {
        abIsPrime[i] = true;
    }
 
    for (int i = 2; i <= MAX_N_VALUE; i++)
    {
        // if [i] is set as prime, 
        if (abIsPrime[i] == true)
        {
            // set [i]'s multiples as NOT prime.
            for (int j = (2 * i); j <= MAX_2N_VALUE; j += i)
            {
                abIsPrime[j] = false;
            }
        }
    }
}
 
int main()
{
    int n, nCount;
 
    checkPrime();
 
    do
    {
        // input n value
        cin >> n;
 
        if (n == 0)    // berak from loop if n is 0
        {
            break;
        }
 
        // Reset count value as 0.
        nCount = 0;
 
        // count prime numbers from (n+1) to (2n).
        for (int i = (n + 1); i <= (2 * n); i++)
        {
            if (abIsPrime[i] == true)
            {
                nCount++;
            }
        }
        // print out result.
        cout << nCount << '\n';
    } while (1);
 
    return 0;
}

원본 링크: https://www.acmicpc.net/problem/4948