에라토스테네스의 체_소수 찾기 [1/1]

[ 에라토스테네스의 체란? ]

• 소수를 구하는 빠른 방법의 알고리즘
• 일반적인 방법 : 해당 숫자를 (2 ~ 해당숫자 -1)번째 수로 차례대로 나눠봄
• 에라토스테네스의 체 : (2 ~ 해당숫자)범위 숫자에서 배수를 모두 지우고 남는 숫자가 소수
• 범위 내 소수를 모두 구할 때 효율적인 방법​

즉 일반적인 방법이 다 나눠보는거라면, 에라토스테네스의 체는 범위 내 숫자의 배수를 모두 지워서 남는 것을 소수로 판단하는 알고리즘입니다.

 

---

 

일단 알고리즘을 배우기 전에 일반적인 코드로 소수를 구해보겠습니다. 사실 이 코드도 매우 간단한데 연산 횟수상에서는 해당 알고리즘에 불리합니다.

 

#include <stdio.h>
#define SIZE 50

void main()
{
	for (int i = 1; i <= SIZE; i++)
	{
		int status = 0;
		for (int j = 2; j < i; j++)
			if (i % j == 0)
			{
				status = 1;
				break;
			}
				
		if(status == 0)
			printf("%d ", i);	
		
	}
}

 

---

 

일반 연산에 비해 에라토스테네스의 체는 효율이 높습니다.

​

예를 들어 1~17 사이의 소수를 구하기 위한 위의 코드에서는 연산 횟수가 46번 이상 발생합니다. 하지만 아래와 같이 에라토스테네츠의 체를 이용하면 대략 23번의 연산이 발생합니다. 물론 범위 확인과 같은 이런저런 곁다리 연산들은 제외한 숫자입니다. 곁다리 연산은 양쪽에 다 있으니 단순 연산 횟수로만 비교해보면 거의 2배의 속도가 차이납니다. 범위가 커질 수록 그 차이는 더 많이 나겠네요.

​

다만 특정 숫자만을 소수 판단하기 위해서는 비효율적입니다. 20이 소수인지 아닌지 판단할 때는 2로만 나눠보면 되는데 에스토스테라스의 체로는 모든 연산을 다 수행해야 합니다.

 

 

배수를 지워줄 때는 무조건 7 * 2, 7 * 3 ... 이렇게 시작하지 않고 7 * 7, 7 * 8 ... 이렇게 시작하는게 효율적입니다. 왜냐면 7 * 6 = 6 * 7 이기 때문에 7 * 6 이란 숫자는 이미 6의 배수를 확인할 때 완료된 숫자이기 때문입니다. 그 전 숫자들도 마찬가지이구요.

 

#include <stdio.h>
#define SIZE 51

void main()
{
	int prime_number[SIZE];
	for (int i = 0; i < SIZE; i++)
		prime_number[i] = i;			// 각 인덱스 값은 본인 숫자

	for (int i = 2; i * 2 < SIZE; i++)
	{
		if (prime_number[i] == 0)		// 이미 지워져있으면 수행하지 않음
			continue;

		for (int w = i, j = i; w * j < SIZE; j++)
			prime_number[w * j] = 0;	// 배수에 있는 값은 0으로 지워줌
	}

	for (int i = 0; i < SIZE; ++i)		// 지워지지 않은 숫자만 출력
		if (prime_number[i] != 0)
			printf("%d ", prime_number[i]);
}