[Algorithhm] 에라토스테네스의 체 알고리즘이란?

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.
이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체 '라고 부른다.

 

---

구현 과정

120까지의 모든 소수를 구한다고 해 보자.
에리스토테네스의 체는 2부터 120까지의 수를 배열에 모두 넣은 후 소수가 아닌 것들으 모두 체크해버리는 것이다.
즉, 체크가 안 된 수들이 소수 이다.

 

 

2. 2를 제외한 2의 배수 지우기

 

2. 3을 제외한 3의 배수 지우기

 

3. 4의 배수는 지울 필요 없다 (2의 배수에서 이미 지워짐)
2,3 다음으로 남아있는 가장 작은 수인 5를 제외한 5의 배수를 지운다.

 

이런 식으로 남은 것들의 2배수, 3배수, ... n배수를 지우다 보면 소수만 남는다.
이미 정해진 소수의 배수인 것들은 지워서 소수를 구하는 방법이 아리스토테네스의 체 이다.

 

📌   근데 2의 배수를 지우고, 3의 배수를 지우고 하면 5의 배수를 지울 때 2,3의 배수들이 이미 한 번 지운게 겹친다.
이런 중복이 없을 때부터 배수를 지우려면 제곱한 수 부터 배수를 지우면 된다.

 

📌   5의 배수를 지운다면, 5의 제곱인 25부터 25+(5 * 1), 25+(5 * 2), 25 + (5 * 3) ... 이런 식으로 배수를 지운다.
이렇게 하면 그 전에 이미 지워져 있는 배수들은 건너 뛰게 된다.

n^2 + i*n // (i는 0부터 증가)

 

---

 

🔥 참고하면 좋은 알고리즘 문제

1. 백준 1929 번 : 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

2. 프로그래머스 : 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기 | 프로그래머스