[C++] 백준 4948

백준의 4948번 문제 베르트랑 공준 문제이다.

https://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이라 가정하면 N ~ 2N 사이의 소수의 갯수를 출력하는 문제이다.

범위를 잘 봐야되는데 N보다 크고 2N보다 작거나 같은 소수의 갯수이기 때문에 범위는 N 초과 2N 이하이다.

N < A <= 2N

 

문제를 푸는데 시간이 꽤나 소요되었다.

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num;
	int count = 0;
    	// n의 크기가 1 <= n <= 123,456이며 n ~ 2n 사이의 소수를 찾아야 하므로 2배
    	// 숫자가 지저분할 것 같아 250,000으로 설정
	int arr[250000];	
						
	while (1) {
		cin >> num;
		if (num == 0)
			return 0;
		else {
        		// arr[2]부터 시작해서 입력된 숫자의 2배되는 범위의 배열에 값 입력
			for (int i = 2; i <= 2 * num; i++) { 
				arr[i] = i;
			}

			for (int i = 2; i <= 2 * num; i++) {
            		// 이미 0으로 초기화 되어있을 경우 continue
				if (arr[i] == 0)					
					continue;
                	// j의 배수들은 전부 0으로 초기화    
				for (int j = 2 * i; j <= 2 * num; j += i) {		
					arr[j] = 0;
				}
			}
			// 배열의 값이 0이 아닐 경우 count 증가
			for (int i = num + 1; i <= 2 * num; i++) {
				if (arr[i] != 0)				
					count++;
			}
		}
		cout << count << "\n";
		count = 0;
	}
}

먼저 배열의 크기는 250,000으로 정했다.

범위가 1<= N <= 123,456인데 2N까지의 값을 저장하기 위해서는 123,456 * 2를 해야 하는데

이러면 숫자가 지저분해서 그냥 올림해서 250,000으로 정하였다.

 

그리고 while문을 사용하여 0이 입력되면 프로그램이 종료되게 하였다.

 

그리고 이번에는 소수를 찾기 위해서 에라토스테네스의 체를 사용하였다.

시간초과가 떠서 더 빠른 방법을 찾게 되었다.

이로써 소수를 구하는 방식을 3가지나 공부하게 되었다.

주먹구구식 나누기 / 제곱근 활용법 / 에라토스테네스의 체

그냥 처음부터 에라토스테네스의 체 알고리즘을 사용했다면 더 빨리 풀었을것 같긴 하다.

 

에라토스테네스의 체는 따로 글을 작성해서 올릴 예정이다.

 

간단히 말하면 2부터 시작해서 배수들을 전부 지워서 남은 수로 소수를 찾는 방식이다.

else {
    	// arr[2]부터 시작해서 입력된 숫자의 2배되는 범위의 배열에 값 입력
	for (int i = 2; i <= 2 * num; i++) { 
		arr[i] = i;
	}
	for (int i = 2; i <= 2 * num; i++) {
         // 이미 0으로 초기화 되어있을 경우 continue
		if (arr[i] == 0)					
			continue;
              // j의 배수들은 전부 0으로 초기화    
		for (int j = 2 * i; j <= 2 * num; j += i) {		
			arr[j] = 0;
		}
	}
	// 배열의 값이 0이 아닐 경우 count 증가
	for (int i = num + 1; i <= 2 * num; i++) {
		if (arr[i] != 0)				
			count++;
	}
}
cout << count << "\n";

핵심되는 부분은 이곳이다.

먼저 각각의 배열에 입력되는 숫자를 집어넣어준다.

그리고 for문을 통해 0으로 초기화가 이미 되어있다면 그대로 지나가고 그렇지 않다면 소수인 수의 배열에 0을 집어넣는다.

이 과정이 처음 소수의 배수들의 배열에 0을 집어넣는 것이다.

그렇다면 0이 아닌 값들이 전부 소수이기 때문이다.

 

그리고 마지막에 for문을 활용하여 배열의 값이 0이 아닐 경우 count를 증가시키고 출력해준다.

 

문제를 이해하는 것과 여러 알고리즘들에 대한 공부의 필요성이 느껴지는 문제인 것 같다.

 

 

 

 + 추가로 기존의 방식을 사용했을 때의 코드이다. 물론 백준에 업로드시 시간초과가 뜬다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num;
	int count = 0;

	while (1) {
		cin >> num;
		if (num == 0)
			return 0;
		for (int i = num+1; i <= 2 * num; i++) {
			if (i == 2 || i == 3) {
				count++;
			}
			for (int j = 2; j <= sqrt(i); j++) {
				if (i % j == 0)
					break;
				if (j == (int)sqrt(i))
					count++;
			}
		}
		cout << count << '\n';
		count = 0;
	}
}