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

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

문제

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

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

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

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

입력

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

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

출력

1 ≤ n ≤ 123,456

---

풀이

Algorithm

• 변수 설명
  • N : 입력값을 받고 저장하는 변수
  • count : N+1부터 2N까지의 소수의 개수를 저장하는 변수
• is_prime 함수 설명

bool is_prime(int n) {
	if ((n <= 1 || n % 2 == 0) && n != 2)
		return false;
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0)
			return false;
	}
	return true;
}

• • 입력으로 받은 수가 소수인지 아닌지 판별하는 함수입니다. 소수라면 true를, 아니라면 false를 return 합니다.
  • 입력받은 수가 1 또는 2가 아닌 짝수라면 우선적으로 false를 return합니다.
  • 그렇지 않다면 자신의 루트보다 작거나 같은 홀수로 나누어 봅니다. 이때 나누었을 때 나머지가 0이 되는 경우, 소수가 아니라는 뜻이므로 false를 return해줍니다.
  • 여기에서 자신의 루트보다 작거나 같은 수로 나누는 이유는, n을 두 수의 곱으로 나타냈을 때 무조건 두 수중 한개는 자신의 루트보다 작거나 같기 때문입니다.
  • 또 홀수로만 나눠보는 이유는, n이 짝수라면 위에서 if문을 통해 걸러졌기 때문에 for문을 돌 수 있는 수는 홀수일텐데, 홀수는 짝수로 절대 나누어질 수 없기 때문입니다.
• 전체적인 알고리즘 설명
  • while문을 통해 N을 입력받습니다. // cin>>N;
  • 이때 입력값이 0이라면 루프를 빠져나옵니다. // if(!N) break;
  • 입력값이 0이 아니라면 N+1부터 2*N까지 수를 모두 탐색한 후에 그 수가 소수라면 count를 1 증가시킵니다.
  • count를 출력해줍니다.
  • 매번 루프를 돌 때마다 count를 0으로 초기화 해주는 것을 잊으면 안돼요!
  • 끝!

code

#include <iostream>
using namespace std;
bool is_prime(int n) {
	if ((n <= 1 || n % 2 == 0) && n != 2)
		return false;
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0)
			return false;
	}
	return true;
}
int main() {
	int N, count;
	while (1) {
		cin >> N;
		count = 0;
		if (!N)	break; //입력이 0이면 루프 빠져나옴
		for (int i = N + 1; i <= 2 * N; i++) {
			if (is_prime(i))
				count++;
		}
		cout << count << '\n';
	}

	return 0;
}