Sieve of Eratosthenes(에라토스테네스의 체)

Sieve of Eratosthenes

수학에서 소수를 찾기 위한 방법중 하나로 고대 그리스 수학자 에라토스테네스가 고안한 방법이다.

 

Prime(소수)

소수는 '양의 약수를 2개만 갖는 자연수'

즉, 자신보다 작은 두개의 자연수를 곱하여 만들수 없는 1보다 큰 자연수로 자기자신과 1의 곱으로만 나타낼수 있는 1보다 큰 자연수를 말한다.

Algorithm

해당 에라토스테네스는 자신보다 작은 두개의 자연수를 곱하여 만들수 없다는 성질을 이용한다.

• 2는 명확히 소수임을 알수 있고 2의 배수는 모두 위의 소수조건을 만족하지 못하므로 소수가 아님을 알 수 있다.
• 3은 2로 인해 지워지지 않았으므로 3보다 작은수의 배수가 아님을 알 수 있고 즉 소수임을 확인할 수 있으며 3의 배수는 소수가 아니므로 3의 배수 또한 지워준다.
• 4의 경우는 2의 배수로 이미 소수가 아님을 확인 할 수 있고, 4의 배수는 모두 2의 배수가 됨을 알 수있다. 즉, 소수가 아님이 판정된 수는 배수가 소수여부를 확인 할 필요가 없다.

Sudo Code

sieve of eratosthenes

1. 소수여부를 구하고자하는 모든 수를 나열(배열 설정)
2. 2의 배수를 모두 지워준다.(2는 소수이므로 지우지 않음)
3. 3의 배수를 모두 지워준다.
4. 지워지지 않은 수의 배수를 지워준다.(지워지지 않은 수는 소수)
5. 해당과정을 계속해서 반복시 소수만 남는다.

Source Code

void setSieveOfEratosthenes(int size) {						//에라토스테네스의 체 설정
  
	bool* primeArr = new bool[size + 1];
	memset(primeArr, true, (size+1) * sizeof(bool));			//초기화
	primeArr[0] = false;
	primeArr[1] = false;

	for (int i = 2; i < sqrt(size); i++) {
 		if (!primeArr[i]) continue;					//소수가 이미 아닌 부분은 무시

		for (int idx = i * 2; idx <= size; idx += i) {
 			primeArr[idx] = false;
  		}
	}
}

Tip...여기서 에라토스테네스의 체의 경우 굳이 구하고자 하는 소수까지 확인할 필요가 없다.

 

배수이기 때문에 구하고자하는 수의 제곱근까지만 확인하면 확인하고자하는 범위의 모든 수를 판별할 수 있다.(처리시간 측면에서 좀 더 이득을 가져갈 수 있다.)