[Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체

에라토스 테네스의 체를 통해서 소수를 판별하는 알고리즘을 알아보겠습니다. [ Contents ] 1. 소수 소수(Prime): 약수가 1과 자기 자신밖에 없는 수 '소수'는 1과 자기 자신으로만 나누어 떨어지는 자연수입니다. 반대로 1과 자기 자신 외에 다른 약수가 있으면 '합성수'라고 합니다. '소수 판별'은 특별한 공식이 없으며, 정의대로 1과 자기자신 사이의 수 중 약수가 있는지 검증해야 합니다. 숫자가 클수록 검증해야 하는 숫자들이 많아지며, 계산복잡도도 높아집니다. 따라서 RSA와 같은 각종 보안 알고리즘에 응용되며, 소수 판별 알고리즘의 중요성도 커지고 있습니다. 만약 소수를 빠르게 찾아낼 수 있는 공식을 찾아낸다면, 블록체인을 비롯해서 사회 전반의 보안 알고리즘을 뚫어낼 수 있습니다. (그럴..

원문링크 : [Algorithm] 소수 판별 알고리즘, 에라토스 테네스의 체