[C++ - TIL] 에라토스테네스의 체를 이용한 효율적인 소수 판별 구현

https://80000coding.oopy.io/51503941-ff71-4cd4-a4cc-ec8a68eddbb7

[TIL 쓸 때 참고할 만한 블로그]

미로찾기 알고리즘 해결 전략 및 구현 (feat. DFS, BFS)

 

🎮 주제 : 에라토스테네스의 체를 이용한 효율적인 소수 판별 구현

태그 : #C++ #알고리즘 #소수판별 #에라토스테네스의체 #동적배열 #메모리관리

---

📌 학습 요약

• 소수(Prime Number)의 정의 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수의 특성을 이해하고 0과 1은 제외됨을 명시
• 제곱근을 이용한 최적화 : 특정 수 $n$이 소수인지 판별할 때, 2부터 $n-1$이 아닌 $\sqrt{n}$까지만 확인해도 충분하다는 수학적 원리 파악
• 에라토스테네스의 체 : 대량의 소수를 구할 때 2부터 시작하여 특정 수의 배수를 순차적으로 지워나가는 효율적인 대량 소수 추출 알고리즘 습득
• 동적 메모리 활용 : new와 delete[]를 사용하여 실행 시간에 결정되는 범위만큼 배열을 할당하고 해제하는 동적 배열 관리 기법 숙지

---

🛠 주요 코드 및 구현 상세

1. 효율적인 개별 소수 판별 (제곱근 활용)

bool isPrime(int n) {
    // 0과 1은 소수가 아님
    if (n < 2) return false;

    // sqrt(n)까지만 검사하여 시간 복잡도를 O(sqrt(n))으로 최적화
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

2. 에라토스테네스의 체 (동적 배열 구현)

void sieve(int n) {
    // 1. n+1 크기의 동적 배열 생성 및 초기화
    int* array = new int[n + 1];
    for (int i = 0; i <= n; i++) array[i] = i;

    // 2. 0과 1은 소수가 아니므로 제외
    array[0] = array[1] = 0;

    // 3. 2부터 루트 n까지 배수 지우기 시작
    for (int i = 2; i * i <= n; i++) {
        if (array[i] != 0) {
            // i 자신은 남기고 i의 배수(j)들만 0으로 처리
            for (int j = i * i; j <= n; j += i) {
                array[j] = 0; 
            }
        }
    }

    // 4. 소수 출력 및 메모리 해제
    for (int i = 2; i <= n; i++) {
        if (array[i] != 0) cout << array[i] << " ";
    }
    
    delete[] array; // 메모리 누수 방지를 위한 해제
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

sqrt()	<cmath> 헤더 포함 필수	반환형이 double이므로 정수 비교 시 주의
new / delete[]	힙(Heap) 영역에 메모리 할당	delete[] 누락 시 메모리 누수 발생
i * i <= n	i <= sqrt(n)과 동일한 의미	정수 연산만으로 처리 가능해 속도가 빠름
배수 제거	j = i * i부터 시작 가능	i * 2보다 i * i부터 지우는 것이 더 효율적

---

✨ 느낀 점

• 에라토스테네스의 체를 구현하며 배수를 지우는 과정에서 소수 자신(자기 자신)까지 지워버리는 실수를 통해 로직의 정교함을 배움
• 단순히 모든 수를 나누어보는 것보다 제곱근($\sqrt{n}$)까지만 확인하는 것만으로도 연산량을 비약적으로 줄일 수 있다는 점이 놀라웠음
• 동적 배열을 직접 관리해보며 할당한 메모리를 delete[]로 해제하는 습관이 프로그램 안정성에 얼마나 중요한지 다시금 깨달음
• 디버깅 과정에서 j < i와 같은 잘못된 루프 조건을 수정하며 코드의 흐름을 한 단계씩 추적하는 훈련이 되었음