C++ 알고리즘 소수구하기 - 에라토스테네스의 체

1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.

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

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

3. 그 수는 소수이다.

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

 

1에서 120까지 소수를 찾는다고 할 때를 생각해보자. 밑의 그림이랑 보면 쉬울 거임!

출처:wikipedia

2부터 120까지 모든 수를 써놓고 아직 지워지지 않은 수 중에서 가장 작은 수를 찾자.

2가 제일 작은 수이고 소수이므로 2의 배수를 모두 지운다. (움짤에 빨간색)

그다음 3이 제일 작은 수이고 소수이므로 3의 배수를 모두 지운다. (움짤에 초록색)

그다음 4는 지워졌고 5가 제일 작은 수이고 소수이므로 5의 배수를 모두 지운다.

그리고 7의 배수를 지우고 이다음 작은 수는 11인데 2, 3, 5, 7에 의해 얘네 * 11은 다 지워져 있고 11*11은 121로 120을 넘기 때문에 더 이상 수행할 필요가 없다.

그래서 남아있는 수(분홍색)가 소수이다.

 

이걸 코드로 짜보자!!

int prime[120]; // 소수 저장
int pn = 0; // 소수의 개수
bool check[121]; // 지워졌으면 true
int n = 120; // 120까지 소수
for (int i = 2; i <= n; i++) {
	if (check[i] == false) { // 지워지지 않음
    	prime[pn++] = i;
        for (int j = i*i ; j <= n; j+=i) {
        	check[j] = true;
        }
    }
}

실제로 숫자를 다 지우면 시간이 많이 걸리기 때문에 여기서는 그냥 지워진 거를 체크된 것으로 코드를 짰다.