Silver_IV 난이도 문제를 C++로 풀이한 내용입니다. 주어진 정수 N보다 크거나 같은 소수 중 가장 작은 수를 찾는 문제입니다.

백준 4134: 다음 소수

Silver_IV 난이도 문제를 C++로 풀이한 내용입니다. 주어진 정수 N보다 크거나 같은 소수 중 가장 작은 수를 찾는 문제입니다.

문제 소개

문제 번호: 4134
문제명: 다음 소수
난이도 (티어): Silver_IV
사용 언어: C++
실행 시간: 220 ms
메모리: 2020 KB
문제 요약: 입력받은 정수 N부터 시작하여, N보다 크거나 같은 소수 중 가장 작은 수를 찾는 문제입니다. 여러 개의 테스트 케이스가 주어집니다.

접근 방법

이 문제는 주어진 숫자 N부터 시작해서 1씩 증가시키면서 해당 숫자가 소수인지 판별하는 방식으로 접근했습니다.

알고리즘/자료구조:
- 소수 판별 알고리즘: 각 숫자가 소수인지 판별하기 위해 가장 기본적인 방법을 사용했습니다.
- 반복문: N부터 시작하여 소수를 찾을 때까지 1씩 증가시키는 반복문.
선택 이유:
- 문제에서 요구하는 바가 "주어진 숫자 N 이상인 가장 작은 소수"이기 때문에, N부터 하나씩 검사하는 것이 가장 직관적이고 명확한 방법입니다.
- 소수 판별의 경우, sqrt(N)까지만 나누어 보면 된다는 것을 활용하여 효율성을 높였습니다.

풀이 과정

입력 받기: 먼저 총 테스트 케이스의 수 T를 입력받습니다.
테스트 케이스 반복: T번 반복하면서 각 테스트 케이스를 처리합니다.
정수 N 입력: 각 테스트 케이스마다 정수 N을 입력받습니다.
소수 찾기 루프: N부터 시작하여 n이라는 변수에 저장하고, n이 소수인지 판별합니다.
- n이 소수이면 n을 출력하고 해당 테스트 케이스를 종료합니다.
- n이 소수가 아니면 n을 1 증가시켜 다시 소수 판별을 진행합니다.
소수 판별: n이 소수인지 판별하는 과정은 다음과 같습니다.
- n이 0 또는 1인 경우 소수가 아닙니다.
- 2부터 sqrt(n) (정확히는 d*d <= n 조건)까지의 수 d로 n을 나누어 봅니다.
- 만약 n이 d로 나누어 떨어진다면, n은 소수가 아닙니다.
- 2부터 sqrt(n)까지의 어떤 수로도 나누어 떨어지지 않으면 n은 소수입니다.
출력: 찾은 가장 작은 소수 n을 출력합니다.

핵심 아이디어

"N부터 시작": 문제의 핵심은 N보다 작지 않은 가장 작은 소수를 찾는 것이므로, N부터 순차적으로 증가시키면서 검사하는 것입니다.
효율적인 소수 판별: sqrt(n)까지만 나누어 보는 것은 소수 판별의 시간을 크게 단축시키는 핵심 최적화 기법입니다. d*d <= n 연산을 사용하면 부동소수점 오류 없이 안전하게 사용할 수 있습니다.

주의할 점

0과 1의 처리: 0과 1은 소수가 아니므로 명확하게 처리해야 합니다.
sqrt의 함정: sqrt 함수는 실수 연산이므로 오차가 발생할 수 있고, 때로는 느릴 수 있습니다. d*d <= n 형태의 정수 연산이 더 안전하고 효율적입니다.
long long 사용: 입력받는 N의 크기가 커질 수 있으므로, 소수 판별 시 n과 d 모두 long long 타입으로 선언하여 오버플로우를 방지해야 합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;

bool isPrime = false;

int main(){
    int T;
    cin >> T;
    
    while(T--) {
        long long N; 
        cin >> N;
        
        
        for(long long n = N; ; n++) { // N부터 시작하여 1씩 증가시키며 소수인지 확인
            // 가정한다
            bool isPrime = true; 
            
            // 0 ≤ n이므로 예외처리
            if(n == 1 || n == 0) isPrime = false; // 1은 소수 아니다

            // 2 이상의 정수로 나누어 떨어지는지 확인하자
            // sqrt(n)은 실수 연산 → 느림 + 오차 가능성
            // d*d <= n은 정수 연산 → 빠르고 정확
            // d ≤ √n ⟺ d^2 ≤ n
            for(long long d = 2; d*d <= n; d++){ // sqrt를 애초에 안쓴다
                if(n % d == 0){ // 나누어 떨어지면
                    isPrime = false; // 소수가 아니다
                    break; // n + 1로 시도해보자
                }
            }
            if(isPrime){ // 위 두가지 판정을 통과했다면
                cout << n << '\n'; // 그 수가 소수다
                break; // 다음 테스트 케이스로 넘어가자
            }
        }
    }
    return 0; // 프로그램 정상 종료
}

주요 부분 설명

#include<bits/stdc++.h>: C++ 표준 라이브러리의 거의 모든 헤더 파일을 포함시켜 편리하게 사용합니다.
using namespace std;: std:: 접두사 없이 표준 라이브러리 요소를 사용할 수 있게 합니다.
long long N;: 입력받는 숫자의 크기가 커질 수 있으므로 long long 타입을 사용합니다.
for(long long n = N; ; n++): N부터 시작하여 무한히 반복하는 루프입니다. break 문을 통해 루프를 탈출합니다.
bool isPrime = true;: 현재 검사 중인 숫자 n이 소수라고 일단 가정합니다.
if(n == 1 || n == 0) isPrime = false;: 0과 1은 소수가 아니므로 isPrime을 false로 설정합니다.
for(long long d = 2; d*d <= n; d++): 소수 판별의 핵심 부분입니다. 2부터 n의 제곱근까지의 수(d*d <= n 조건을 통해 구현)로 나누어 떨어지는지 확인합니다.
if(n % d == 0): n이 d로 나누어 떨어지면 n은 소수가 아닙니다.
isPrime = false; break;: 소수가 아님을 표시하고 내부 루프를 종료합니다.
if(isPrime) { cout << n << '\n'; break; }: n이 소수로 판별되면 출력하고 외부 루프(while(T--))를 탈출합니다.
return 0;: 프로그램이 성공적으로 실행되었음을 나타냅니다.

복잡도 분석

시간 복잡도:
- 각 테스트 케이스에서 N부터 시작하여 다음 소수 P를 찾는 데까지 P - N + 1번의 반복이 필요합니다.
- 소수 판별 함수는 O(sqrt(n))의 복잡도를 가집니다.
- 최악의 경우, N이 아주 큰 소수이고 바로 다음 소수가 N에서 멀리 떨어져 있다면 시간이 오래 걸릴 수 있습니다. 예를 들어, N이 매우 큰 짝수일 경우 N+1부터 시작하여 소수를 찾아야 합니다.
- 대략적으로, N이 k자리 숫자라면 log10(N)이 k에 비례합니다. 다음 소수를 찾는 데 걸리는 횟수는 대략 log(N) 정도라고 알려져 있습니다.
- 따라서 전체 시간 복잡도는 대략 O(T * log(N) * sqrt(N)) 으로 볼 수 있습니다. (여기서 log(N)은 다음 소수를 찾기까지의 평균적인 탐색 횟수입니다.)
공간 복잡도:
- O(1)입니다. 입력받는 변수들과 몇 개의 지역 변수만 사용하므로, 입력 크기에 비례하는 추가적인 메모리를 사용하지 않습니다.

배운 점

이 문제를 풀면서 다음과 같은 점들을 다시 한번 확인할 수 있었습니다.

소수 판별의 효율적인 방법: sqrt(n)까지만 검사하는 것이 소수 판별의 표준적인 최적화 기법임을 상기할 수 있었습니다. d*d <= n 형태의 정수 연산을 사용하는 것이 실수 연산보다 더 안전하고 빠르다는 것을 배웠습니다.
long long 타입의 중요성: 입력값의 범위를 고려하여 적절한 데이터 타입을 선택하는 것이 중요함을 다시 한번 깨달았습니다. 특히 소수 판별 과정에서 중간 계산 결과가 커질 수 있으므로 long long을 사용하는 것이 필수적입니다.
문제 조건의 철저한 이해: "N보다 크거나 같은"이라는 조건을 놓치지 않고 N부터 시작하는 루프를 설계하는 것이 문제 해결의 핵심이었습니다.
코드의 가독성: 주석을 통해 각 부분의 역할을 명확히 설명하여 코드의 이해를 돕는 것이 중요합니다.

이러한 기본적인 알고리즘 지식과 주의사항들은 다른 소수 관련 문제나 수론 문제들을 해결하는 데 있어 좋은 밑거름이 될 것입니다.