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

1. 문제이해

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

 

입력받은 자연수 n에 대해 n보다 크고, 2n보다 작거나 같은 수 중

소수의 개수를 출력하는 것이 목표이다.

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

 

 

 

2. 문제풀이

 

주어진 n에 대해, n < x <= 2n 인 자연수 x중 소수의 개수를 판정하는 문제이다.

또한, 0 이 입력되면 자동으로 프로그램은 종료되어야 한다.

 

일반적인 소수판정 문제에 몇가지 조건이 추가된 문제이다.

해당 자연수(N)가 소수인지를 판단하기 위해서는,

2부터 N-1까지의 숫자로 나누어보고, 나누어떨어지는 숫자가 있다면 소수가 아닌것으로 판단.

나누어 떨어지는 수가 없다면 소수인 것으로 판단하면 된다.

 

하지만 위와 같은 방식으로 하면, 주어진 시간을 초과하게 되므로,

이전 포스팅에서 사용했던 방식인 제곱근을 이용한 알고리즘을 채택했다.

위의 방식과 거의 동일하나, 자연수(N)이 소수인지 판단할 때, 2부터 N의 제곱근 값까지만 검사하여,

나누어 떨어지는 수가 있다면 소수가 아닌것으로 판단하는 방식이다.

이 방법을 사용하면, 검사하게 되는 범위가 반으로 줄어 시간초과를 예방할 수 있게 된다.

자세한 내용은 아래 포스팅을 참고하자.

https://beginnerdeveloper-lit.tistory.com/65

[C++] 백준 1929번 소수 구하기

 

 

 

 

3. 소스코드

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

int main() {
	int n = 1;             // n 초기화 (숫자는 상관없음)
	int count;             // 소수의 개수
	int not_prime_num;     // 소수가 아닌 것을 구분하기 위함
	int root;              // 해당 수의 루트값  

	while (n != 0) {	// 0이 입력되면 코드 종료
		cin >> n;
		count = 0;

		if (n == 1) {	// n이 1인 경우
			count = 1;
		}

		else {			
			for (int i = n + 1; i <= (2 * n); i++) {
				root = (int)sqrt(i);     // 루트값 이용해 시간초과 방지
				not_prime_num = 0;

				for (int j = 2; j <= root; j++) {
					if (i % j == 0) {    // 나누어지는 수가 있다면
						not_prime_num++; // 해당 변수값 증가
						break;
					}

				}

				// not_prime_num값이 0이면 나누어떨어진 수가 없는 것 = 소수
				if (not_prime_num == 0) {  
					count++;               // 소수의 개수 카운트
				}
			}
		}
		
		// 0이 입력된 경우에도 count 출력됨을 방지하기 위함
		if (n != 0) {	
			cout << count << endl;
		}
	}

	return 0;
}

우선, 위와 같이 변수들을 설정해준다.

이때, 자연수 n은 while문 이용 시 초기화가 필요하므로 1로 초기화해주었다.

(숫자는 다시 입력받아 초기화 되기때문에 어떤 수던지 상관없다.)

 

while문을 통해, n이 0이 입력되면 자동으로 종료되도록 하고,

소수의 개수는 각 테스트 케이스인 n이 입력될 때마다 0으로 초기화 해준다.

if문을 통해 입력받은 n값이 1이라면, 소수의 개수(count)는 1이라고 지정하고,

이외의 경우에는 for문 연산을 통해 소수의 개수를 세어준다.

 

else문 안의 for문에서는 n + 1 부터 2n 까지 소수의 개수를 세어준다.

2. 문제풀이에서 얘기했듯, 제곱근값을 이용해 해당 수의 제곱근값까지만 검사하고,

만약, 나누어떨어지는 값이 있다면 not_prime_num 값을 증가시킨다.

not_prime_num값은 소수와 소수가 아닌 수를 판단하기 위해 사용하는 변수로,

for문 연산이 끝나고 not_prime_num 값이 0이면 소수이므로, 소수의 개수(count)를 카운트한다.

 

마지막으로, 최종적인 소수의 개수(count) 값을 출력하게 되는데,

이때, n = 0인 경우 프로그램이 바로 종료되지 않고 count 값이 출력되고 종료되는 것을 방지하기 위해

if문을 통해 0이 아닌 경우에만 count 값을 출력해주었다.

 

 

---

저번에 풀이했던 제곱근을 이용한 풀이방식을 몰랐다면 상당히 애를 먹었을 것 같은 문제이다.😭

더 많은 문제들을 접해보고 연습해봐야지✍