에라토스테네스의 체

에라토스테네스의 체는 대표적인 소수(Prime Number) 판별 알고리즘이다.

에라토스테네스의 체 알고리즘은 한 두개의 소수를 판별하는 경우가 아닌 대량의 소수를 한꺼번에 판별할 때 사용한다.

 

에라토스테네스의 체는 우선 예를 들어 1부터 100까지의 수에서 소수를 판별한다고 하면 크기가 101인 int형 배열을 선언한다. 그리고 초기에 각 인덱스는 인덱스의 값으로 초기화를 시켜준다.

 

그 후 반복문을 통해 2의 배수, 3의 배수 ,4의 배수, ... 에 해당하는 인덱스의 값을 0으로 바꿔주는데 시간 복잡도를 줄이기 위해 이미 0인 부분은 continue를 사용하여 스킵되도록 한다.

 

#include <iostream>

using namespace std;
int number = 100;
int a[101];

void isPrimeNumberSieve() {
	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue;
		for (int j = i + i; j <= number; j += i) {
			a[j] = 0;
		}
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] != 0)
			printf("%d ", a[i]);
	}
}

int main() {
	isPrimeNumberSieve();
	return 0;
}

그러면 위와 같이 대량의 소수를 판별해내는 것을 확인할 수 있다!