알고리즘

에라스토테네스의 체

서론 에라스토테네스의 체 코딩 테스트에서 자주 등장하는 알고리즘 중 하나인 '에라스토테네스의 채'를 이용한 소수 찾기 방법에 대해 알아보겠습니다. 이 방법은 특정 범위 내에서 소수를 효과적으로 찾는데 사용됩니다. 방법 1. 2부터 시작하여, 특정 수 N까지의 모든 수를 나열합니다. 2. 아직 지워지지 않은 수 중 가장 작은 수를 찾습니다. 이 수는 소수입니다. 3. 그 소수의 배수를 모두 지웁니다. 4. 남아있는 수 중에서 다시 가장 작은 수를 찾고, 이를 반복합니다. 예제 #include #include int main() { int N = 100; // 소수를 찾을 범위 설정 std::vector prime(N + 1, true); // 모든 숫자를 소수로 가정 // 에라스토테네스의 채 알고리즘 적용..