[BOJ / 백준] 4948번 베르트랑 공준 C++ 문제 풀이

단계별로 풀어보기 - 수학 2단계 - [4단계] 4948번

문제

문제 링크 : www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

입력 복사 : 

1 10 13 100 1000 10000 100000 0

 

CODE

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

int main() {
	int n, rt, cnt = 0;

	while (1) {
		cin >> n;
		if (!n)	//0 입력시 종료
			break;

		for (int i = n + 1; i <= 2 * n; i++) {
			rt = sqrt(i);
			if (rt == 1 && i != 1) {	//2,3인 경우
				cnt++;
				continue;
			}
			if (i % 2) {	//홀수일 경우
				for (int j = 2; j <= rt; j++) {
					if (!(i%j))
						break;
					if (j == rt) {
						cnt++;
					}
				}
			}
		}
		cout << cnt << '\n';
		cnt = 0;
	}
}

 

풀이

이전 소수 구하기 문제와 같은 방식으로 해결하였다.

검사 범위를 n+1부터 2*n까지로 변경하여 소수를 카운트하였다.

 

결과