백준 4948) 베르트랑 공준 (c)

#include<stdio.h>
int main()
{
	int decimal[246913] = { 0, }; //소수면 0 아니면 1 123456*2+1
	decimal[0] = 1, decimal[1] = 1; //0 1 은 소수가 아니므로 미리 선언 
	int i = 0;
	int j = 0;
	int N = 1;
	for (j = 2; j < 246913 / j; j++)
	{
		if (decimal[j] == 1) continue; //소수가 아니면 통과 
		for (i = j * j; i < 246913; i += j)
		{
			if (i % j == 0) decimal[i] = 1;
		}
	}
  scanf("%d",&N);  //첨부터 0 나오면 종료시켜줘야되니 처음은 while밖에 선언 
	while(N!=0)
  {
    int count=0;   //반복마다 count 초기화 
    for(i=N+1;i<=2*N;i++)
    {
      if(decimal[i]==0) count++; //소수면 count++
    }
     printf("%d\n",count);
     scanf("%d",&N);
  }
}

앞의 소수 구하기를 참고해서 풀어봤다. 

일단 최대 N에 들어갈 수 있는 123456값의 2배 만큼 곱한 후 1을 더하고

미리 소수를 구해놓고 풀어봤다.