[C++] 에라토스테네스의 채(The Sieve of Eratosthenes)

[C++] 에라토스테네스의 채(The Sieve of Eratosthenes)

소수(Prime Number)는1과 자기 자신밖에 약수가 없다는 특징 때문에 암호학에서 자주 사용되는 방법이기도 하고, 소인수 분해에서도 사용된다.

어떤 수를 입력받아서 소수인지 아닌지 판별하는 방법은 1을 제외하고, 입력받은 수 보다 작은 수로 약분이 되는지를 모두 검사하면 된다. 그렇다면 만약에 누군가가 1부터 100사이의 소수를 모두 출력하라고 한다면, 1부터 100사이의 수를 모두다 이처럼 검사할 것인가? 가능은 하지만 너무 오래걸린다.

이런 상황에서는, 1부터 N까지의 모든 소수를 구할 수 있는 "에라토스테네스"의 채 알고리즘을 사용하면 된다. 이 알고리즘의 원리는 소수와 어떤 수의 곱은 반드시 소수가 아님을 이용한 것인데, 마치 채로 거르듯이 소수가 아닌 수들을 채에서 걸러내고, 결국 채에서 빠져나온 소수들만 남기는 원리이다.

#include <iostream>
#include <string.h>//memset함수를 사용하려면 선언해야함
using namespace std;
bool arr[101];
int main()
{
	memset(arr, true, sizeof(arr)); // 배열 값을 true로 초기화
	arr[1] = false;
	int it = 2;
	//2부터 100까지 소수의 배수인 수 들을 모두 false로(소수가 아닌 수)로 바꿈.
	while (it<=50) {
		if (arr[it]) {
			int m = 2;
			while (it*m < 101) {
				arr[it*m] = false;
				m++;
			}
		}
		it++;
	}
	cout << "1부터 100 사이의 소수는 아래와 같습니다." << endl;
	for (int i = 1; i < 101; i++) {
		if (arr[i]) {
			cout << i << " ";
		}
	}
	cout << endl;
}