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

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

4948번: 베르트랑 공준

n이 소수인지 아닌지 알아보려면 제곱근 n까지만 나눠보면 된다.

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


int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		int count = 0;
		for (int num = n + 1; num <= 2 * n; num++) {
			bool flag = true;
			if (num % 2 == 1) {
				for (int i = 3; i <= sqrt(num); i++) {
					if (num % i == 0) {
						flag = false;
						break;
					}
				}
			}
			else {
				flag = false;
			}
			if (num == 2) flag = true;
			if (num == 1) flag = false;
			if (flag) count++;
		}
		cout << count << '\n';
	}
	return 0;
}