[BAEKJOON] 4948번

<C>

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int input;
    int count = 0;
    int i, j;
    int* result = (int*)malloc(sizeof(int));
    int idx = 0;
    int isComp[246913] = { 0 };
 
    for (i = 2; i < sizeof(isComp) / sizeof(int); ++i)
    {
        if (isComp[i] == 0)
        {
            for (j = 2*i; j < sizeof(isComp) / sizeof(int); j += i)
            {
                isComp[j] = 1;
            }
        }
    }
 
    while(1)
    {
        scanf("%d", &input);
        
        if (!input) { break;}
 
        for (i = (input + 1); i <= (2 * input); ++i)
        {
            if (!isComp[i])    { ++count; }
        }
 
        result = realloc(result, sizeof(int) * (idx + 1));
        result[idx++] = count;
        
        count = 0;
    } 
    
    for (i = 0; i < idx; ++i)
    {
        printf("%d\n", result[i]);
    }
    
    return 0;
}

역시나 에라토스테네스의 체.

입력값의 범위는 1<=123456이므로 인덱스에 매핑하기 위해 배열의 크기는 2×123456 + 1로 

한다.

또한 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수이므로

for문의 반복조건은  i = input + 1; (i <= 2 * input) 이다.