백준 4948 - 베르트랑 공준

이 문제는 소수를 찾는 것이 핵심이였다. 나는 우선 300000까지의 소수를 모두 구한 다음 for을 통해 소수의 갯수를 구하는 방법을 사용하였다. 

소수 구하는 방법은 에라토스테네스의 체를 사용하였다. 

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

#include <iostream>
#include <algorithm>
using namespace std;

int dp[300000];

int main() {
	// 소수 구하기
	dp[0] = 1, dp[1] = 1;
	for (int i = 2; i < 300000; i++) {
		if (dp[i] == 1)continue;
		for (int j = i * 2; j < 300000; j += i) {
			dp[j] = 1;
		}
	}
	while (1) {
		int n;
		cin >> n;
		if (n == 0)break;
		int ans = 0;
		for (int i = n + 1; i <= 2 * n; i++) {
			if (dp[i] == 0)ans++;
		}
		cout << ans << '\n';
		
	}
}