[C++] 에라토스테네스의 체

• 순서
  1. 소수란?
  2. 에라토스테네스의 체란?
  3. 에라토스테네스의 체 사용 이유
  4. 에라토스테네스의 체 원리
  5. 에라토스테네스의 체 구현
• 소수란?
  1. 소수란 1보다 크며 1과 자신으로만 나누어지는 수
• 에라토스테네스의 체란?
  1. 소수를 판별하는 알고리즘.
  2. 많은 수의 소수들을 빠르고 정확하게 구하는 방법
• 에라토스테네스의 체 사용이유
  1. 소수를 판별해야하는 상황 중 "2부터 N까지 수 중 소수 찾기"와 같이 특정 범위 수 중에서 소수를 찾는 데 사용할 수 있는 효율적인 방법이기 때문
• 에라토스테네스의 체 원리
  1. 각 수에 대해 그 수의 배수를 모두 제거하는 작업을 수행
  2. 2의 배수를 제거할 때 n/2번, 3의 배수를 제거할 때 n/3번...방식을 반복함
     • 시간 복잡도는 n/2 + n/3 + n/4 + ... + 1 = n( n/2 + n/3 + n/4 )가 된다.
  3. 여기서 1/2 + 1/3 + 1/4 + ...는 조화 급수로, 그 합이 loglogn에 근접함
  4. 이로 인해 전체 시간 복잡도는 O(nloglogn)이 
• 에라토스테네스의 체 구현
  • vector<bool> 배열의 인덱스로 숫자를 대체하고 2부터 탐색하기 때문에 n까지 판별하기 위해 n+1의 크기로 생성
  • 배수에 해당하는 숫자는 false로 처리하고 마지막까지 true로 남은 숫자가 소수가 되는 코드

vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime; // isPrime[i]가 true면 i는 소수
}