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

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

4948번: 베르트랑 공준

---

 

 

○ n은 123,456까지 입력될 수 있고 문제에서 n보다 크고 2n보다 작거나 같은이라는 범위를 주었다.

 

○ 123456*2크기만큼의 배열을 만든 후 에라토스테네스의 체 공식을 이용하여 소수가 아닌 수들의

    배열에 값을 주자.

 

○ while문을 사용해 n을 입력받고 0이면 break를 통해 종료

 

○ n+1부터 2n까지 반복문을 통해 배열에 값이없는 수(소수들)을 체크하고 count+=1을 해준다.

 

#include<stdio.h>

int main() {
	int n;
	int count = 0;
	int c[123456*2] = { 0 };
	c[1] = 1;
	for (int i = 2; i <= 123456*2; i++)
		for (int j = 2; j * i <= 123456*2; j++)
			c[i * j] = 1;

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