[백준 BOJ] 4948번 베르트랑 공준 (C++/cpp)

문제 설명

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

4948번: 베르트랑 공준

 

접근 방법 - 에라토스테네스의 체 알고리즘을 응용한 소수 판정 문제

백준의 4948번 문제는 에라토스테네스의 체 알고리즘을 통해 소수를 판별해야 하는 문제이다.

해당 문제는, 각 케이스의 입력값 n에 대하여 n보다 크고 2n보다 작거나 같은 소수의 개수를 구하여 출력해야 하는 문제이다.

에라토스테네스의 체 알고리즘에 대한 설명은 이전 ps글에서 다룬 적이 있어 이에 대한 링크를 아래에 기재해놓았다.

해당 알고리즘이 어색하다면, 아래의 링크도 함께 참고해보길 바란다.

https://smary-it.tistory.com/157

[백준 BOJ] 2960번 에라토스테네스의 체 (C++/cpp)

이 알고리즘만 능숙하게 다룰 수 있다면 크게 어렵지는 않을 문제로 생각된다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 에라토스테네스의 체 알고리즘을 수행하기 위한 배열(arr)을 전역 변수로 미리 선언해둔다.

 

2) 아래처럼 알고리즘을 수행한다. (연산 방법에 대해 이미 알고 있다면 이 설명은 넘어가도 좋다.)

(여기서, arr의 배열값이 0이라면 소수임을 뜻하며 1이라면 소수가 아님을 뜻한다고 가정한다.)

- 우선 0과 1은 소수가 아니기 때문에, 해당 인덱스의 배열값을 1로 변경한다.

- 2부터 시작하여 자기 자신을 제외한 배수들을 인덱스로 갖는 배열값들을 모두 1로 변경한다.

자기 자신을 제외한 소수의 배수들은 소수가 아니라는 점을 이용한 것이다.

 

3) 무한 반복문을 실행하여 아래의 연산을 실행한다.

- n을 입력받는다. (이때, 0을 입력받으면 해당 무한 반복문을 종료하도록 한다.)

- 소수의 개수를 연산할 변수 cnt를 0으로 초기화하여 선언한다.

- n보다 크고 2n보다 작거나 같은 소수를 arr를 통해 탐색한다.

만일 해당 위치의 arr의 배열값이 0이라면, 이는 소수라는 것을 뜻하기 때문에 cnt에 1을 더한다.

- 연산이 완료된 cnt를 출력한 뒤, 다음 입력값에 대한 연산을 취하도록 한다.

 

4) 모든 케이스에 대한 연산이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 4948번 코드
int arr[250000];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	arr[0] = 1;	arr[1] = 1;
	for (int i = 2; i <= 123456; i++) {
		if (arr[i] != 0) { continue; }
		for (int j = 2; i * j < 250000; j++) {
			arr[i * j]++;
		}
	}

	while (1) {
		int n;
		cin >> n;
		if (n == 0) { break; }

		int cnt = 0;
		for (int i = n + 1; i <= 2 * n; i++) {
			if (arr[i] == 0) { cnt++; }
		}
		cout << cnt << endl;
	}
}

 

제출 결과

(2022.06.04 백준 4948번 문제 제출 결과)