[알고리즘] 에라토스테네스의 체 (C++) - 소수 찾기

 

간혹 소수 찾기 혹은 소인수분해 관련해서 문제를 풀때면,

 

소수들을 어떻게 구해야하나라는 문제에 직면한다.

 

보통 아래와 같이 생각하여 코드를 구현하지만

시간초과라는 문제에 직면하게 될 확률이 높다.

 

- for문 돌려서 소인수 확인하기

for(int i=2; i<N; i++){
	if(N%i==0){
    	printf("N은 소수가 아닙니다.")
    } else {
    	printf("N은 소수 입니다.")
    }
}

 

대표적으로 "에라토스테네스의 체"라는 소수 구하는 방법이 있다.

 

구체적인 방법은 아래와 같다.

 

ㅇ 에라토스테네스의 체란?

에라토스테네스의 체

2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.

1. 2부터 시작해서 n까지 진행한다.
2. 가장 작은 수를 선택한다.
3. 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.

• 시간복잡도 : O(n*log(log(n)))

 

ㅇ 에라토스테네스의 체 코드 구현

//에라토스테네스의 체로 1000까지의 소수 출력하기

#include<stdio.h>
#include<cmath>
using namespace std;


int main(){
	int n = 1000;
	int check[1001] = { false };

	check[0] = check[1] = true;
	for (int i = 2; i < sqrt(1000); i++){
		if (check[i] == false){
			for (int j = i + i; j <= 1000; j += i){
				check[j] = true;
			}
		}
	}

	for (int i = 1; i <= n; i++){
		if (!check[i]) printf("%d ", i);
	}
	


	return 0;
}