에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법이다. 여기서 소수는 1과 자기자신을 약수로 가지는 모든 자연수이며,

 

대표적으로 2, 3, 5, 7, 11, 13, ... 등이 존재한다.

 

우선, 에라토스테네스의 체를 사용하지 않고 기본적인 소수 판별 코드는 다음과 같다.

 

[소수 판별 기본 코드]

#include <stdio.h>

bool isPrimeNumber(int x) {
	for(int i=2; i<x; i++) {
		if(x%i == 0) return false;
	}
	return true;
}

int main() {
	printf("%d ", isPrimeNumber(97));
}

 

메인코드에서 전달받은 x의 값을 i로 나누고 나머지 값이 0 이라면 소수가 아니기 때문에 false 즉, 0을 반환하고

 

나머지 값이 0이 아니라면 true, 즉 1을 반환한다. 결과적으로, 97은 소수이기 때문에 1을 반환한다.

---

하지만 이러한 방식으로 소수를 판별한다면 모든 경우의 수를 다 돌며 약수 여부를 확인하기 때문에 굉장히 비효율적이다.

 

이러한 문제점을 에라토스테네스의 체를 통해 해결할 수 있다. 에라토스테네스의 체의 알고리즘 과정은 다음과 같다.

 

(1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열하고 자기 자신 즉, 2를 제외한 2의 배수를 모두 지운다.

 

(2) 자기 자신 즉, 3을 제외한 3의 배수를 모두 지운다.

 

(3) (1)번을 통해 4가 지워졌으므로 넘어가고, 5를 제외한 5의 배수를 모두 지운다.

 

(4) (1)번을 통해 6이 지워졌으므로 넘어가고, 7을 제외한 7의 배수를 모두 지운다.

 

(5) 위와 같은 과정을 반복하면 구하는 구간의 모든 소수가 남게 된다.

 

[에라토스테네스의 체의 소수 판별 코드]

#include <stdio.h>

int number = 100000;
int a[100001];

void primeNumberSieve() {
	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() {
	primeNumberSieve();
}

 

위와 같은 에라토스테네스의 체의 알고리즘 과정을 코드로 구현하였다. 

 

100000개의 수에 대하여 소수를 판별하도록 하였고 자기 자신의 인덱스로 그 값을 초기화한다.

 

두번째 반복문에서 특정한 수의 배수들을 모두 지워주도록 하고 이미 지워진 수들은 넘어간다.

 

위와 같은 반복과정이 끝난 후에 최종적으로 지워지지 않고 남겨진 인덱스 값을 출력하면 소수임을 확인할 수 있다.

---

출처

https://blog.naver.com/ndb796/221233595886

22. 에라토스테네스의 체