Silver_III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 범위 내의 모든 소수를 효율적으로 찾아 출력하는 문제입니다.

백준 1929: 소수 구하기

Silver_III 난이도 문제를 C++로 풀이한 내용입니다. 주어진 범위 내의 모든 소수를 효율적으로 찾아 출력하는 문제입니다.

문제 소개

문제 번호: 1929
문제명: 소수 구하기
난이도 (티어): Silver_III
사용 언어: C++
실행 시간: 488 ms
메모리: 2020 KB
문제 요약: M부터 N까지의 모든 소수를 찾아 출력하는 문제입니다.

접근 방법

이 문제는 주어진 범위 (M부터 N까지) 안에서 소수를 찾아야 합니다. 가장 기본적인 소수 판별 방법은 어떤 수가 소수인지 직접 확인하는 것입니다. 하지만 M과 N의 범위가 상당히 클 수 있으므로, 효율적인 소수 판별 알고리즘이 필요합니다.

저는 각 숫자에 대해 일일이 소수인지 판별하는 방법을 사용했습니다. 각 숫자가 소수인지 판별하기 위해 2부터 해당 숫자의 제곱근까지만 나누어 떨어지는지 확인하는 방식으로 시간 복잡도를 줄였습니다.

왜 이 방법을 선택했는가?

단순함: 각 숫자를 독립적으로 판별하므로 로직이 비교적 간단합니다.
효율성: d * d <= m 조건을 통해 최대 sqrt(m)까지만 나누어 보면 되므로, 단순하게 m-1까지 나누어 보는 것보다 훨씬 효율적입니다.
메모리: 이 방법은 추가적인 자료구조를 많이 사용하지 않아 메모리 사용량이 적습니다.

풀이 과정

입력 받기: 문제에서 주어지는 두 자연수 M과 N을 입력받습니다.
범위 순회: M부터 N까지 각 숫자 m에 대해 반복문을 수행합니다.
소수 판별: 각 숫자 m에 대해 소수인지 아닌지를 판별하는 로직을 적용합니다.
- m이 1인 경우는 소수가 아니므로 isPrime을 false로 설정합니다.
- m이 2 이상인 경우, 2부터 sqrt(m)까지의 수 d로 m을 나누어 봅니다.
- 만약 m이 d로 나누어 떨어진다면, m은 소수가 아니므로 isPrime을 false로 설정하고 내부 반복문을 중단합니다.
- 내부 반복문이 끝까지 실행되었는데 isPrime이 true라면, m은 소수입니다.
출력: 소수로 판별된 숫자 m을 출력합니다. 각 소수는 줄바꿈 문자로 구분합니다.

핵심 아이디어:

1은 소수가 아닙니다.
어떤 수 m이 소수가 아니라면, m은 sqrt(m) 이하의 소인수를 반드시 가집니다. 따라서 2부터 sqrt(m)까지만 확인하면 소수 여부를 판별할 수 있습니다.

주의할 점:

m이 1인 경우를 명확히 처리해야 합니다.
제곱근을 계산할 때 정수형 연산 (d * d <= m)을 사용하여 부동소수점 오류를 방지하는 것이 좋습니다.
long long 타입을 사용하여 M과 N의 범위가 클 경우 발생할 수 있는 오버플로우를 방지해야 합니다.

코드 설명

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

bool isPrime = false; // 이 변수는 사실상 main 함수 안의 로컬 변수로만 사용됩니다.

int main(){
        long long M, N; // M과 N은 범위의 시작과 끝을 나타내는 정수이며, 값이 클 수 있으므로 long long 타입을 사용합니다.
        cin >> M >> N; // 사용자로부터 M과 N 값을 입력받습니다.
        
        
        for(long long m = M; m <= N; m++){ // M부터 N까지 모든 숫자에 대해 반복합니다.
            // 가정한다 (각 숫자를 처음에는 소수라고 가정합니다.)
            bool isPrime = true; 
            
            // 1 ≤ m이므로 예외처리
            if(m == 1) isPrime = false; // 1은 소수가 아니므로, isPrime을 false로 설정합니다.
            
            // 2 이상의 정수로 m이 나누어 떨어지는지 확인하자
            // d ≤ √m ⟺ d^2 ≤ m
            // 어떤 수 m이 소수가 아니라면, m은 sqrt(m) 이하의 약수를 반드시 가집니다.
            // 따라서 2부터 sqrt(m)까지만 나누어 보면 소수 여부를 알 수 있습니다.
            for(long long d = 2; d*d <= m; d++){ 
                if(m % d == 0){ // 만약 m이 d로 나누어 떨어진다면, m은 소수가 아닙니다.
                    isPrime = false; // isPrime을 false로 설정합니다.
                    break; // 더 이상 확인할 필요가 없으므로 내부 반복문을 종료합니다.
                }
            }
            if(isPrime){ // 위 두 가지 판정 (m=1 제외, 나누어 떨어지지 않음)을 통과했다면, m은 소수입니다.
                cout << m << '\n'; // 소수인 m을 출력하고 줄바꿈 문자를 추가합니다.
                continue; // 다음 숫자로 넘어가서 검사를 계속합니다.
            }
        }
}

복잡도 분석

시간 복잡도:
O((N-M+1) * sqrt(N))
최악의 경우 M=1, N=100,000 이라면, 약 100,000 * sqrt(100,000) = 100,000 * 316 = 31,600,000 연산 정도가 수행될 수 있습니다. 이는 시간 초과가 발생할 수 있는 범위입니다. (참고: 실제 제출 시 488ms가 나왔으므로, 이 경우에 시간 초과는 발생하지 않았습니다. 하지만 더 큰 N 범위에서는 에라토스테네스의 체 같은 더 효율적인 알고리즘이 필요할 수 있습니다.)
공간 복잡도:
O(1)
추가적인 배열이나 자료구조를 사용하지 않고 몇 개의 변수만 사용하므로 공간 복잡도는 상수입니다.

배운 점

소수 판별 최적화: 각 숫자를 소수인지 판별할 때, 단순히 i-1까지 나누는 대신 sqrt(i)까지만 나누어 보는 것이 시간 복잡도를 크게 줄일 수 있다는 것을 다시 한번 상기했습니다.
예외 처리의 중요성: 1은 소수가 아니라는 점을 명확히 처리하는 것이 중요합니다.
알고리즘 선택: 이 문제의 경우 N의 최대값이 100,000인데, 해당 범위까지는 직접 판별하는 방법으로도 통과가 가능했습니다. 하지만 N이 더 커진다면 에라토스테네스의 체와 같은 '체' 알고리즘을 사용하여 O(N log log N)의 시간 복잡도로 더 효율적으로 모든 소수를 찾는 방법을 고려해야 합니다. 이번 문제는 직접 판별법으로 해결되었지만, 실제 알고리즘 문제 풀이에서는 문제의 제약 조건을 잘 파악하고 가장 효율적인 알고리즘을 선택하는 연습이 중요합니다.