[C++] 백준 4948번: 베르트랑 공준

문제

난이도 : 실버 2
백준 4948번 : 베르트랑 공준

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 123456;
int n;
bool arr[2 * MAX + 4];

void Func()
{
    arr[0] = arr[1] = true;

    for (int i = 2; i <= 2 * MAX; i++)
    {
        if (arr[i] == false)
        {
            for (int j = i * 2; j <= 2 * MAX; j += i)
            {
				arr[j] = true;
			}
		}
	}
}

int main()
{
    Func();

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

        int answer = 0;

        for (int i = n + 1; i <= 2 * n; i++)
        {
            if (arr[i] == false)
            {
                cout << i << ' ';
                answer++;
            }
        }
        
        cout << answer << "\n";
    }

    return 0;
}

설명

소수를 판별하는 문제. 입력받은 n부터 2n까지 for문을 돌려가며 소수인지 아닌지를 판별해가는 방식은 시간 초과가 걸린다.
그래서 에라토스테네스의 체를 사용해 배열으로 각 인덱스가 소수인지 아닌지를 판별해 저장해놓은 다음 n+1부터 2n까지 반복문을 돌려가며 소수이면 카운팅하는 식으로 접근해야 함.
에라토스테네스의 체는 소수 문제에서 많이 이용되므로 구글링을 통해 공부해두고 어떻게 구현하는지도 어렵지 않아 쉽게 외울 수 있을 것이다.

결과