8월 10일(수) - 8단계(4948번)

8단계 - 4948번

4948번: 베르트랑 공준

 

문제점

1. 직전 문제처럼, 에라토스테네스의 체를 활용하면 된다

-> 이에 대한 공부가 필요한 상황이다.

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int main(void)
{
    int N, cnt = 0;
    int i, j, arr[246913] = { 0, };

    arr[0] = 1, arr[1] = 1;
    for (j = 2; j < 246913 / j; j++)
    {
        if (arr[j] == 1) continue;
        for (i = j * j; i < 246913; i += j)
            if (i % j == 0) arr[i] = 1;
    }
    scanf("%d", &N);

    while (N != 0)
    {
        cnt = 0;
        for (i = N + 1; i <= N * 2; i++)
            if (arr[i] == 0)
                cnt++;
        printf("%d\n", cnt);
        scanf("%d", &N);
    }
    return 0;
}

 

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