관리 메뉴
목록2025/08/27 (1)
개발자공부일기
에라토스테네스의 체
에라토스테네스의 체란?에라토스테네스의 채(Sieve of Eratosthenes)는 소수 판별 알고리즘이다.특정 범위(예: 1 ~ N) 안에 존재하는 모든 소수를 효율적으로 찾기 위해 고안되었다.핵심 아이디어는어떤 수가 소수라면, 그 수의 배수들은 모두 소수가 아니다.따라서 소수를 하나씩 찾으면서, 그 소수의 배수를 지워 나가면 된다.1.알고리즘 흐름2부터 N까지를 모두 후보로 둔다.아직 지워지지 않은 가장 작은 수 p를 찾는다. p는 소수다.p의 배수들을 지운다. (보통 p*p부터 지운다)p를 다음 수로 옮기며, p ≤ √N일 동안 반복한다.남은 수가 모두 소수다.2. 동작 과정예를 들어 N = 30 까지의 소수를 구한다고 하자.초기화2부터 30까지 모든 수를 후보로 둔다. (1은 소수가 아니므로 제외..
코딩테스트/알고리즘
2025. 8. 27. 18:10