[c++/백준] 4948 베르트랑 공준

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

4948번: 베르트랑 공준

에라토스테네스의 체를 사용해서 구하는 문제이다. 개인적으로 실2까진 아닌 것 같다. 

#include <iostream>
using namespace std;

int arr[1000000];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	while (1) {
		cin >> n;
		int cnt = 0;	//cnt 초기화
		if (n == 0) {	//while문 탈출 조건
			break;
		}
        
        //에라토스테네스의 체
		for (int i = 2; i <= 2 * n; i++) {
			arr[i] = i;
		}
		for (int i = 2; i <= 2 * n; i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j = i + i; j <= 2 * n; j += i) {
				arr[j] = 0;
			}
		}
		for (int i = n + 1; i <= 2 * n; i++) {
			if (arr[i] != 0) {
				cnt++;
			}
		}
		cout << cnt << '\n';
	}
}

그치만 난 에라토스테네스의 체 잘 모르니께 걍 외워버려야지