[c++/알고리즘] 에라토스테네스의 체

에라토스테네스의 체는 유명한 소수 구하기 문제이다. 

시간 복잡도가 O(N^1/2)이기 때문에 많은 양의 소수를 구할 때 유용하게 사용할 수 있다.

 

원리는 간단하다. 2의 배수인 수를 모두 지운 후 2는 옆에 적어준다. 이후 지워지지 않은 가장 작은 수(n) 부터 n의 배수를 지워주고 n을 옆에 적어주면 된다. 

<c++ 코드로 구현하기>

#include <iostream>
using namespace std;

int n = 120;
int main() {
	ios::syn_with_studio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	int arr[121];
    
    //배열에 값 입력
	for (int i = 2; i <= n; i++) {
		arr[i] = i;
	}
	for (int i = 2; i <= n; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i + i; j <= n; j+=i)	//i의 배수 지우기 (배열의 i값 0으로 만들기)
			arr[j] = 0;
	}
	for (int i = 2; i <= n; i++) {
		if (arr[i] != 0) {
			cout << arr[i] << " ";
		}
	}
}

궁금한 점은 댓글로 편안하게 물어봐주세요! 물론 저도 모를지도,,