4장 수학 - (6) 에라토스테네스의 체

1. 어떤 수 N이 소수인지 아닌지 알아내는데 걸리는 시각 복잡도가 O(루트N) 이라고 하면,

1부터 N까지 범위에서 모든 소수를 구하는데 걸리는 시간 복잡도는 O(N루트N) 만큼의 시간이 걸린다.

N이 백만인 경우, 1,000,000 * 1,000 = 10^9 = 10억 = 10초 가 걸린다.

너무 긴 시간이 필요하므로 이 경우에는 에라토스테네스의 체를 사용한다.

2. 에라토스테네스의 체

-1부터 N까지 범위 안에 들어가는 모든 소수를 구할 때 사용

1)2부터 N까지 모든 수를 써놓는다.

2)아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3)그 수는 소수이다.

4)이제 그 수의 배수를 모두 지운다.

(코드)

N이 100 이라고 하면,

int p[100]; // 소수 저장

int pn=0; // 소수의 개수

bool c[101]; // 지워졌으면 true

int n=100; // 100까지의 소수

for(int i=2;i<=n;i++){

if(c[i]==false){

p[pn++]=i;

for(int j=i*i;j<=n;j+=i){ // j는 i에 i보다 작은 수가 곱해진 경우는 이전에 이미 지워졌으므로, i*i 부터 시작

c[j]=true;

}

}

}

=> 이 때, 안쪽 for문에서 j는 N의 크기에 따라서, i*i 또는 i*2로 바꿔도 된다.(지운것을 또지워도 상관없으므로) i가 10^6인 경우 범위를 벗어나기 때문

-1929번(소수 구하기)