[Algorithm] 에라토스테네스의 체를 통해 소수구하기
소수를 구할 때 가장 빠른 시간에 구할 수 있는 에라토스테네스의 체의 방법을 알아보자
환경 및 선수조건
- C++
에라토스테네스의 체
2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.
- 2부터 시작해서 n까지 진행한다.
- 가장 작은 수를 선택한다.
- 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.
- 시간복잡도:
O(n*log(log(n)))
코드
- count: 저장된 소수의 개수
- c[n+1]: 2 ~ n까지 수에서 제거된 숫자를 체크하는 배열, true(제거됨), false(제거되지않음)
- p[n]: 소수를 저장하는 배열
example.cpp
bool c[1000001]= {false,};
int p[1000000];
int count = 0;
//0~1000000까지 소수 구하기
for(int i=2; i<=1000000; i++){
if(c[i] == false){
// 추가
p[count++] = i;
// i의 배수 지우기
for(int j=i+i; j<=1000000; j+=i){
c[j]=true;
}
}
}