[Tech, Algo] Sieve of Eratosthenes (에라토스테네스의 체)

에라토스테네스의 체는 소수를 찾아내기 위한 알고리즘으로, 교과 과정에서도 배우는 내용 중 하나다. 이 알고리즘은 LeetCode 204. Count Primes 와 같은 인터뷰에도 종종 등장하므로 알고 있으면 매우 유용하다. 고대 그리스 수학자 에라토스테네스가 발견한 이 알고리즘은 '체'로 치듯이 수를 걸러낸다고 해 '에라토스테네스의 체'로 불린다. 이 알고리즘의 포인트는 배수와 제곱근을 활용하는 것이다. 예를 통해 이해해보자. 1부터 100까지의 숫자 중 소수를 찾는다 가정하자. 1부터 100까지의 숫자를 나열해보자. 작은 숫자부터 시작을 하고, 특수한 경우인 1을 우선 지운다. 2를 제외한 2의 배수를 지운다. (배수 활용 시작) 3을 제외한 3의 배수를 지운다. 4의 배수는 이미 2의 배수를 통해 ..
기술(Tech, IT)/알고리즘(Algorithm) 2024. 3. 12. 00:49
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형