[백준 BoJ] 4948 - 베르트랑 공준

// https://www.acmicpc.net/problem/4948
// 베르트랑 공준
#include<iostream>

using namespace std;
bool is_prime(int num) {
	if (num == 1) return false;

	for (int i = 2; i*i <= num; i++) {
		if (num%i == 0) return false;
	}
	return true;
}
int main() {
	int N;
	
	while (1) {
		cin >> N;
		int cnt = 0;

		if (N == 0) break;

		for (int i = N + 1; i <= N * 2; i++) {
			if (is_prime(i)) cnt++;
		}
		cout << cnt << "\n";
	}
}

cmath 라이브러리에 있는 sqrt를 이용해 구현했지만 시간초과가 뜸. i<=sqrt(num)

i * i <= num 으로 변경후 시간 초과 안뜸.