에라토스테네스의 체란?
에라토스테네스의 체는 소수를 찾아야 하는 상황에 쉽게 사용할 수 있는 알고리즘이다. 2부터 시작해 해당 배수들을 배열에서 모두 제외시키는 원리인데, (ex.2의배수 4,6,8,10... 제외, 3의배수 3,6,9,12,15... 제외.. ) 이 연산이 끝났을 때 배열에는 자연스럽게 소수만 남게 된다. 코드로 나타내면 다음과 같다.
static boolean[] visited = new boolean[MAX];
static int[] prime = new int[MAX];
static void prime_numbers() {
for(int i=2; i*i<visited.length; i++) { // 제곱근까지 검사
if(!visited[i]) { // 기본값이 false이므로 false라면
for(int j=i*i; j<visited.length; j+=i) { // 해당숫자의 배수들을 모드 true로 처리
visited[j] = true;
}
}
}
for(int i=2; i<MAX; i++) {
if(!visited[i])
prime[size++] = i; // 위에서 완성된 visited배열을 활용해 소수를 순차적으로 담는 prime 배열 생성
}
} 왜 제곱근 까지만 검사해도 하는가?
쉽게 이야기하면 자연수의 약수는 대칭을 띄고 있기 때문이다. 예를 들어 64의 약수는 1,2,4,8,16,32,64인데, 가운데 8을 기준으로 양 옆으로 대칭되는 숫자들 끼리 곱하면 64를 만들 수 있다. ( 1 x 64, 2 x 32, 4 x 16 )
여기서 코드와 연관지어 생각 해보면 다음과 같다.
1. 2의 배수를 제거하는 과정에서 2 x 32는 제거가 된다.
2. 2 x 32는 32 x 2로 나타낼 수도 있다.
3. 32의 배수를 제거하는 과정이 있다면 32x2를 제거하는 상황이 발생하는데, 이는 중복된 연산이다.
4. 따라서 원하는 범위의 제곱근까지만 계산하면 불필요한 연산을 줄일 수 있다.
주의사항?
에라토스테네스의 체는 시간복잡도가 O(nlog(logn)) 일반적으로 가장 빠른 소수 판별법이지만,
n의 크기가 매우 크게 주어지는 특정 문제에서는 이중 for문을 활용한 단순한 방식이 유리한 경우가 있다.
쉿! 공부중