에라토스테네스의 체

[Algorithm] 에라토스테네스의 체

[Algorithm] 에라토스테네스의 체 (글쓴날 : 2020.03.23) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 에라토스테네스의 체 1) 에라토스테네스의 체란? 에라토스테네스의 체란 소수를 구할 때 사용되는 매우 유용한 알고리즘입니다. 소수란 1과 자신을 제외한 약수가 없는 1이 아닌 자연수를 뜻하며, 이러한 소수를 원하는 범위까지 효율적으로 구하고 싶다면 에라토스테네스의 체를 사용하시면 됩니다. 에라토스테네스의 체의 주요 원리는 정해진 숫자의 범위 내에서 합성수를 지우는 방식으로, 처음 1은 소수가 아니니 지우고, 남아있는 수 중 제일 작은 숫자인 2를 소수로 판별하여 2의 배수를 모두 지웁니다. 똑같이 남아있는 수 중 제일 작은 수인 3을 소수로 판별하여 3의 배수를 모조리 ..