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

 에라토스테네스의 체(Sieve of Eratosthenes)는 소수를 빠르게 찾는 알고리즘으로, 주어진 범위 내의 모든 소수를 효율적으로 찾는 방법이다.

알고리즘 개요

 2부터 시작하여, 현재 수가 소수라면 그 수의 배수를 모두 리스트에서 지우고 다음 소수를 찾아 반복한다. 리스트에 남아 있는 숫자들이 소수이다.

예시

예를 들어, 𝑛=30일 때 에라토스테네스의 체를 사용하여 소수를 찾는 과정은 다음과 같다.

초기 리스트: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
2의 배수 제거: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 제거
다음 소수 3: 6, 9, 12, 15, 18, 21, 24, 27, 30 제거
다음 소수 5: 10, 15, 20, 25 제거
다음 소수 7: 14, 21, 28 제거
최종적으로 남은 수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 소수이다.

시간 복잡도

에라토스테네스의 체의 시간 복잡도는 𝑂(𝑛log(log𝑛))으로, 매우 효율적인 알고리즘으로 큰 범위에서 소수를 찾을 때 사용하면 좋다.

코드

#include <iostream>

using namespace std;

bool isPrime[100000];

void FindPrime(int n) {
	for (int i = 2; i <= n; i++) 
		isPrime[i] = true;

	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {//현재 수가 소수라면,
			cout << i << ' ';
			for (int j = 2 * i; j <= n; j += i) //현재 수의 배수는 소수가 아니다
				isPrime[j] = false;
		}
	}
    cout << '\n';
}

int main() {
	int n;
	cin >> n;

	FindPrime(n);

	return 0;
}