2022-08-25-bertrand-4948

• toc {:toc}

문제

베르트랑 공준은 임의의 자연수 n 에 대하여, n 보다 크고, 2n 보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845 년에 추측했고, 파프누티 체비쇼프가 1850 년에 증명했다.

예를 들어, 10 보다 크고, 20 보다 작거나 같은 소수는 4 개가 있다. (11, 13, 17, 19) 또, 14 보다 크고, 28 보다 작거나 같은 소수는 3 개가 있다. (17,19, 23)

자연수 n 이 주어졌을 때, n 보다 크고, 2n 보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n 을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0 이 주어진다.

출력

각 테스트 케이스에 대해서, n 보다 크고, 2n 보다 작거나 같은 소수의 개수를 출력한다.

제한

• 1 ≤ n ≤ 123,456

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

풀이

1. is_prime 함수를 통해 함수인지 아닌지 판별 후 개수를 카운트함.
2. 문제 조건 확실하게 확인하기 (중요!)

#include <iostream>
 
using namespace std;
 
bool is_prime(int n);
 
int main() 
{
  	int inp, num;
	
	while(true)
	{
		num = 0;
		cin >> inp;
		if(inp==0) break;
		for(int i=inp+1; i<=2*inp; i++)
		{
			if(is_prime(i))
			{
				num++;
			}
		}
		cout << num << endl;
	}
	
	return 0;
}
 
bool is_prime(int n)
{
	int i = 2;
	for(i; i*i<=n; i++)
	{
		if(n%i==0)
			return false;
	}
	return true;
}