[백준 BOJ] 4134번 다음 소수 (C++/cpp)

문제 설명

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

4134번: 다음 소수

 

접근 방법 - 브루트포스 알고리즘을 응용한 소수 판정 문제

백준의 4134번 문제는 브루트포스 알고리즘을 활용하여 소수 판정 연산을 해야 하는 문제이다.

해당 문제는, 각 입력값보다 크거나 같은 소수들 중 최솟값을 찾아내어 출력해야 하는 문제이다.

여기서 소수는, 약수를 1과 자기 자신만을 갖는 숫자를 칭하는 것이다.

사실 소수 판정에 있어선 에라토스테네스의 체 알고리즘이 가장 흔한 알고리즘이다.

다만, 입력값이 워낙 광범위하기 때문에 해당 문제는 브루트포스 알고리즘을 활용하여 해결해보았다.

응용해본 방법은 아래 코드가 있으니, 혹여나 해결에 어려움을 겪고 있다면 아래의 코드와 설명을 참고해보길 바란다.

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

 

코드의 실행 순서

1) 테스트 케이스의 수(n)를 입력받는다.

 

2) n의 크기만큼 반복문을 수행하여 아래의 연산을 취한다.

- 값(a)을 입력받는다.  (여기서, 입력값의 범위를 고려하여 unsigned int로 입력받았다.)

만일 여기서 a의 값을 0, 1, 2로 받은 경우 정답은 2이기 때문에, 2를 출력한 뒤 다음 순서의 반복문을 실행한다.

- 무한 반복문을 만들어 아래처럼 실행하도록 한다.

(1) 약수의 개수를 카운팅할 변수 cnt를 0으로 초기화하여 선언한다.

(2) 2부터 a의 제곱근+1까지 하여 이 중에 현재 a의 약수가 있는지 탐색한다.

만일 여기에서 a의 약수가 발견되었다면 이는 소수가 아니다. 따라서 이 경우엔 cnt에 1을 더한 뒤 약수 탐색을 종료한다.

(3) cnt가 0인 경우, 이는 소수로 판정된다. 따라서 이때엔, 현재의 a 값을 출력한 뒤 현재 테스트 케이스를 종료한다.

다만 cnt가 0이 아닌 경우엔 아직 소수를 찾지 못한 경우이다. 따라서 이때엔, a에 1을 더한 뒤 소수 탐색을 계속 진행한다.

 

3) 모든 테스트 케이스에 대한 정답이 출력되었다면, 실행 종료한다.

반응형

 

성공한 코드

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

//백준 4134번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		unsigned int a;
		cin >> a;
		if (a == 0 || a == 1 || a == 2) {
			cout << 2 << endl; continue;
		}

		int cnt;
		while (1) {
			cnt = 0;
			for (unsigned int j = 2; j <= sqrt(a) + 1; j++) {
				if (a % j == 0) { cnt++; break; }
			}
			if (cnt == 0) {
				cout << a << endl;	break;
			}
			a++;
		}
	}
}

 

제출 결과

(2022.07.01 백준 4134번 문제 제출 결과)