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

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

문제 접근법

 1. 에라토스테네스의 체를 이용해서 최대 범위까지의 소수를 구한다. (배열을 활용)

 2. n을 입력받고 주어진 범위 내의 소수의 갯수를 카운트해서 출력

느낀점

처음에 단순하게 함수를 만들어서 n 값을 입력 받을 때마다 계산하는 쪽으로 생각했다. 하지만 주어진 시간은 1초였고 찾아보니 에라토스테네스의 체라는 소수 찾는 알고리즘이 있었다. 이번 기회로 새로운 알고리즘을 공부했지만 계속 소수 문제가 나와서 너무 재미가 떨어졌다.

코드

#include <stdio.h>
#define size 246913

int main() {
	int arr[size] = { };
	arr[0] = arr[1] = 1;
	for (int i = 2;i * i <= size;i++) {
		if (!arr[i]) {
			for (int j = i * i;j <= size;j += i) arr[j] = 1;
		}
	}

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

	return 0;
}