에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로,
이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다.

에라토스테네스의 체 원리

2를 제외한 2의 배수를 모두 거르고,
3을 제외한 3의 배수를 모두 거르고,
4는 걸러진 수이므로 넘어간다.
다시 5를 제외한 5의 배수를 거르기를 반복하면서
남은 수들을 소수로 판별할 수 있다.

단일 숫자 소수 여부 확인

대량의 수는 에라토스테네스의 체를 사용하는게 효과적이겠지만,
필요한 해당 숫자의 소수여부 판별은 그 수만 찾아주는게 효과적이다.

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문이다.

관련문제

백준 - 1929 소수구하기
프로그래머스 - 소수만들기