에라토스테네스의 체5 [알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes) 목차 에라토스테네스의 체란? 에라토스테네스의 체는 소수 판별 알고리즘이다. 소수란 ‘양의 약수를 두 개만 가지는 자연수’를 뜻한다. 즉, 1과 자기 자신만 약수로 가진다. 소수의 예시로는 2, 3, 5, 7, 11, 13 등이 있다. 에라토스테네스의 체는 이런 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 우선 먼저 가장 기본적인 소수 판별 알고리즘들을 살펴보겠다. 시간 복잡도 O(N) boolean isPrime(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } 자연수 n이 소수인지 아닌지 판별하는 가장 쉬운 방법은 2부터 n - 1까지의 수로 나누어 떨어지는지 아닌지 확인하는 것이다. 이때, .. 2022. 7. 15. 이전 1 2 다음 반응형
