에라토스테네스의 체

"에라토스테네스의 체" 를 첫번째 기본 알고리즘으로 선택한 이유는 간단하다.

지워나가는 규칙만 알면 손쉽게 풀 수 있기 때문,

우선 1의 배수란 모든 수를 의미하기 때문에, 에라토스테네스의 체는 2부터 시작한다.

아래 그림과 같이 숫자 2부터 시작해서 2의 배수를 제거해나간다. (물론 이때, 2는 포함하지 않게된다. 2는 소수!)

그다음, 다음 수인 3부터 또 다시 지워지며 쭉~ 해당되는 N(임의의 수) 까지 진행되게 된다.

물론 위에 그림처럼 같은 수를 중복해서 제거해 주어도 되지만, 최대한 중복된 계산을 피하기 위해서 우리는 visit라는 임의의 bool 변수를 이용하여

중복된 것은 건너 뛰도록 한다.

임의의 N 수에 대한 에라토스테네스의 체는 아래와 같은 소스코드로 작성가능하다.

 (문제 예시로 보려면, 카테고리 <알고리즘 매일 2문제> 로 이동하여 확인가능하다)

<소스코드>

int sosu_number[N],cnt;

void era(int N) {
	for (int i = 2; i*i <= N; i++) {
		if (!visit[i]) {
			for (int j = i * 2; j <= N; j += i) {
				visit[j] = true;
			}
		}
	}

	for (int i = 2; i <= N; i++) {
		if (!visit[i]) sosu_number[cnt++] = i;
	}
}