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

수학에서는 에라토스테네스의 체는 소수를 찾는 방법이다.

체. 걸러내는 이미지가 있다. 계속 걸러내서 소수를 찾는 방법이다.

자. 이렇게 걸러서 흰색 배경 숫자들이 소수가 된다.

그러면 100까지 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 된다.

 

자. 여기에서 의문점이 들 수 있다. 왜 11, 13은 확인 안하는가?

한번 넣어보자. 11  * 2 / 11 * 3 / ... / 11 * 9  -> 전부 색이 이미 칠해져 있다. 이유는 알 것이다. 2, 3, 5, 7을 지우면서 이미 다 지웠던 숫자들이다. 그러니까 소수를 판별할 때 11 * 11부터 색을 칠하면 되는 것이다. 하지만 11 * 11은 100을 넘어가기 때문에 따로 지울 필요는 없다. 

이 방식을 이용하여 소수를 판별할 수 있다.

이 알고리즘과 관련한 간단한 문제를 풀어보자.

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

1978번: 소수 찾기