[알고리즘] 에라토스테네스의 체

알고리즘

• 초기 sieve 배열의 모든 값은 0으로 초기화되어 있습니다.
• 2부터 차례대로 정수를 살펴 봅니다.
• 2가 소수입니다. 따라서, 2의 배수들은 sieve[x] = 1로 전부 표시해 놓습니다.
  • 이럴 경우 sieve[4] = sieve[6] = sieve[8] = … = 1이 됩니다.
• 이제 다음 숫자를 살펴봅니다. (sieve[x] == 1인 x는 살펴보지 않고 반복문상에서 건너뛸 수 있습니다.)
• 3은 sieve[3] = 0 이었습니다. 따라서 소수이며, 3의 배수들은 전부 1로 표시해 놓습니다.
• 4를 봅니다. 4는 이미 sieve[4] = 1이므로 건너뜁니다.
• 5를 봅니다. sieve[5] = 0 이므로 소수이며, 5의 배수들은 전부 1로 표시해 놓습니다.
• …

C++ 코드

#include <iostream>
#include <cmath>

int main() {
	int arr[1000000] = { 0, };

	for (int i = 2; i <= n; i++) {
		arr[i] = i;
	}
    
	for (int i = 2; i <= sqrt(n); i++) {
		if (arr[i] == 0) continue;
		for (int j = i + i; j <= n; j += i) {
			arr[j] = 0;
		}
	}

 }