[C언어] 백준 4948번 베르트랑 공준

에라토스테네스의 체를 이용해 배열을 미리 채워놓고, 

입력을 받을 때마다 배열을 조회하면서 해당 구간의 소수의 개수를 세어 출력한다.

 

※ n = 0일때는 출력을 하지 않고 프로그램을 종료시켜야 한다.

#include <stdio.h>

int main()
{
	int n, i, j, cnt;
	char ns[246913] = {1,1};

	for (i = 2; i * i < 2 * 123456 + 1; i++)
		if (!ns[i])
			for (j = i * i; j < 2 * 123456 + 1; j += i)
				ns[j] = 1;

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

	return 0;
}