[4948] 백준 : 베르트랑 공준(C++)

 

* 접근 방법
- 에라토스테네스의 체(이전 포스팅 참고)

2020/04/26 - [알고리즘 공부] - [1978] 백준 : 소수 찾기(C++)

2020/04/26 - [알고리즘 공부] - [2581] 백준 : 소수(C++)

 

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

int main()
{
	vector<int> num(123456 * 2 + 1, 0);
	while (1)
	{
		int answer = 0;
		int N;
		cin >> N;
		if (N == 0) break;
		
		num[1] = 1;
		for (int i = 2; i*i <= 123456 * 2; i++)
		{
			if (num[i] == 0)
				for (int j = i * i; j <= 123456 * 2; j += i)
					num[j] = 1;
		}

		for (int i = N + 1; i <= 2 * N; i++)
		{
			if (num[i] == 0) answer++;
		}
		cout << answer << "\n";
	}

	return 0;
}