백준 4948: 베르트랑 공준

Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 문제입니다.

문제 소개

• 문제 번호: 4948
• 제목: 베르트랑 공준
• 난이도: Silver_II
• 사용 언어: C++
• 실행 시간: 544 ms
• 메모리: 2020 KB

문제 요약: 여러 테스트 케이스에서 n을 입력받아 n보다 크고 2n보다 작거나 같은 범위 내 소수의 개수를 출력합니다. 입력의 마지막은 0입니다.

접근 방법

문제를 n+1부터 2n까지의 수 중 소수를 세는 것으로 이해했습니다.
소수 판정 알고리즘을 사용했습니다.
이 방법을 선택한 이유는 범위가 1 ≤ n ≤ 123456이므로 각 테스트 케이스마다 개별 소수 판정을 수행할 수 있습니다.

풀이 과정

1. n을 입력받습니다.
2. n이 0이면 종료합니다.
3. n+1부터 2n까지 각 수에 대해 소수 판정을 수행합니다.
4. 소수 판정: 1이나 0은 소수가 아니며, 2부터 √n까지 나누어 떨어지는지 확인합니다.
5. 소수 개수를 세서 출력합니다.

핵심 아이디어: 각 수에 대해 제곱근까지만 나누기 검사하여 효율적으로 소수 판정.
주의할 점: n=1일 때 21=2까지만 검사하며, 루프에서 dd <= n 조건 사용.

코드 설명

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

bool isPrime = false;

int main(){
    while(1){
        int N; 
        cin >> N;
        if(N == 0){ // 입력의 마지막에는 0이 주어진다.
            return 0;
        }
        
        int prime_cnt = 0;
        // n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력
        for(int n = N + 1; n <= 2 * N; n++){
            // 가정한다
            bool isPrime = true; 
            
            // 0 ≤ n이므로 예외처리
            if(n == 1 || n == 0) isPrime = false; // 1은 소수 아니다
            
            // 2 이상의 정수로 나누어 떨어지는지 확인하자
            // 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){ // 위 두가지 판정을 통과했다면
                prime_cnt++; // 그 수가 소수다
            } // 이제 n+1이 소수인지 확인해보자
        }
        
        cout << prime_cnt << '\n';
        prime_cnt = 0;
    }
}

주요 부분 설명:

• 전역 isPrime 변수는 사용되지 않으며, 루프 내에서 로컬 isPrime 사용.
• for(long long d = 2; d*d <= n; d++)로 제곱근 검사 구현.
• 코드 주석이 풀이 과정을 설명합니다.

복잡도 분석

시간 복잡도: 각 테스트 케이스에서 O((n log n)) (에라토스테네스의 체 대신 개별 판정). n=123456일 때 123456 * √123456 ≈ 10^7 연산.
공간 복잡도: O(1) (배열 사용 안 함).

배운 점

소수 판정에서 제곱근 검사를 d*d <= n으로 구현하는 방법.
입력 반복 처리에서 0으로 종료하는 패턴.