Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다…

기타 알고리즘 : 에라토스테네스의 체

다수의 소수 판별

하나의 수에 대해서 소수 여부를 판단하는 방법과 달리, 다수의 소수를 찾아야 하는 경우에는
에라토스테네스의 체 알고리즘을 사용해야 합니다.

에라토스테네스의 체 알고리즘

다수의 자연수에 대하여 소수 여부 판별을 하는 대표적 알고리즘입니다.
에라토스테네스의 체는 N 보다 작거나 같은 모든 소수를 찾을 때 사용하면 됩니다.
구체적인 동작 과정은 다음과 같습니다.
1. 2부터 N까지 모든 자연수를 나열합니다.
2. 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾습니다.
3. 남은 수 중 i의 배수를 모두 제거합니다(i는 제거하지 않습니다.)
4. 더 이상 반복할 수 없을 때까지 2, 3과정을 반복하고 나면 체에 거르듯 소수를 걸러낼 수 있습니다.

알고리즘 예시 코드

Python

import math

# 2부터 1000까지 모든 수를 초기화합니다.
n = 1000
array = [True for i in range(n + 1)]

# 에라토스테네스의 체 알고리즘을 수행
for i in range(2, int(math.sqrt(n)) + 1):
	if array[i] == True:
		# i 를 제외한 i의 모든 배수가 최대 숫자보다 적게까지 계산되고 False 처리가 됩니다.
		# 이때 i의 다음 값들 중 False가 되니 자동으로 가장 작은 True값만 다음으로 지정하여 처리됩니다.
		j = 2
		while i * j <= n:
			array[i * j] = False
			j += 1

for i in range(2, n + 1):
	if array[i]:
		print(i, end=' ')

C++

#include<bits/stdc++.h>

using namespace std;

int n = 1000;
vector<int> arr(n + 1, true);

int main(void)
{
	for (int i = 2; i <= n; i++)
	{
		if (arr[i] == true)
		{
			int j = 2;
			while(i * j <= 2)
			{
				arr[i * j] = false;
				j += 1;
			}
		}
	}
	for (int i = 2; i <= n; i++)
		if (arr[i])
			cout << i << ' ';
}

에라토스테네스의 체 알고리즘의 성능 분석

해당 알고리즘의 시간은 사실상 선형 시간에 가깝게 매우 빠릅니다. 이를 좀더 구체적으로 정리하면 다음과 같습니다.
𝑂(𝑁𝑙𝑜𝘨𝑙𝑜𝘨𝑵)
해당 알고리즘은 다수의 소수를 찾아야 하는 문제에서 아주 효과적입니다. 그러나 각 자연수에 대한 소수 여부를 저장하므로 메모리가 많이 필요합니다.
따라서 10억이 소수인지 아닌지를 판별이 이걸로 가능할까요?
- 위의 예시의 경우 공간복잡도가 대폭 늘어나게 됩니다. 경우에 따라서 메모리 사용이 쉽지 않을 수 있습니다(물론, 해당 힙영역을 활용하여 할당을 직접 해주는 방식이라면… 가능할 수 있습니다.

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻

Introduction
기타 알고리즘 : 에라토스테네스의 체