소수찾기

[Algorithm] 에라스토테네스의 체 : 소수 구하기

#에라스토테네스의 체 에라스토테네스의 체란 일정 범위 내의 소수를 찾는 가장 효율적인 알고리즘이다. 알고리즘의 원리는 어떤 수의 배수는 소수가 될 수 없다는 원리에 착안하여, 어떤 수의 배수가 되는 수들을 지워나가는 식이다. 1. 2 ~ N 까지의 자연수 중 먼저 소수를 찾는다(해당 범위에서는 2부터 시작됨) 2. 그 소수(2)를 제외한, 나머지 N까지의 수 중 우리가 찾은 소수(2)의 배수들을 모두 지운다. 3. 다음 소수(3)를 찾고 이 수를 제외한, 나머지 N까지의 수 중 방금 우리가 찾은 소수(3)의 배수들을 모두 지운다. 4. 위 과정을 N의 제곱근까지 반복한다(소수점은 내림한다). 해당 과정을 반복하고나면, 지워지고 남은 수들이 모두 소수가 된다. #구현 #include #include #de..