[BEAKJOON] 4948_베르트랑 공준_C언어

https://www.acmicpc.net/problem/4948

풀이

에라토스테네스의 체를 이용하여 소수들을 모두 구한 후, n+1이상 2n이하의 소수의 개수를 출력하면 되는 문제.

에라토스테네스의 체는 간단히 설명하면 2를 제외한 2의 배수들을 전부 소수에서 제외, 3을 제외한 3의 배수들을 소수에서 제외 하는 방식으로 2부터 숫자를 증가하면서 소수를 구해나간다.

제출한 코드

#include <stdio.h>
int arr[246913];
int main() {
    arr[1] = arr[0] = 1;
    for (int i = 2; i < 246913; i++)//에라토스테네스의 체
    {
        if (!arr[i])
        {
            for (int j = i + i; j < 246913; j += i)//배수들을 소수에서 제외
                arr[j] = 1;
        }
    }
    while (1)
    {
        int N, cnt = 0;
        scanf("%d",&N);
        if (!N) break;
        for (int i = N + 1; i <= 2 * N; i++)//개수 카운트
        {
            if (!arr[i])
                cnt++;
        }
        printf("%d\n",cnt);
    }
}