에라토스테네의 체

에라토스테네스의 체는 소수를 찾는 방법이다.

 

2부터 시작해서 소수의 배수들을 모두 제거하는 알고리즘을 통해 대량의 소수를 구할 수 있다.

#define bigNum 1000000001
bool primeNumber[bigNum];

void setPrime() {
	for (int i = 2; i < bigNum; i++) {
		primeNumber[i] = true;
	}

	for (int i = 2; i < bigNum; i++) {
		if (!primeNumber[i]) continue;

		for (int j = 2 * i; j < bigNum; j += i) {
			primeNumber[j] = false;
		}
	}
}

10^9개의 소수를 구하는데 약 18초가 소요된다.