[프로그래머스] 소수 찾기(Feat. 에라토스테네스의 체)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12921

이 문제는 에라토스테네스의 체 방식으로 풀 수 있습니다. 우선 에라토스테네스의 체에 대해 알아보겠습니다.

에라토스테네스의 체란 소수를 찾는 알고리즘으로, 1부터 N까지 소수의 개수를 구할 때 주로 사용합니다. 우선 2부터 자기 자신을 제외한 배수들을 모두 걸러냅니다. 이후 수를 1씩 증가시키면서 자기 자신을 제외한 배수들을 걸러냅니다. 이 때 이미 걸러진 수를 탐색하지 않아도 되므로 시간이 절약되는 효과를 가집니다.

여기서 구현 시 하나의 팁이 있습니다. 이미 걸러진 수를 탐색하지 않기 위해선 이전에 탐색을 진행한 수의 배수와의 공배수는 피해야 합니다. 예를 들어 이미 2를 탐색한 상황에서 3을 탐색할 경우 두 수의 공배수인 6의 배수는 탐색하지 않아야 한다는 것입니다. 만약 단순히 모든 수를 탐색하면서 소수 판별 여부를 체크했는지 안했는지를 한번 더 체크한다면 체크하는 시간만큼 성능이 떨어지게 됩니다.

따라서 수 i가 소수일 경우 탐색을 진행하는 인덱스는 iXi 부터 i씩 증가시키면서 탐색을 진행하야 합니다. 즉 i X (i+0), i X (i+1), i X (i+2) ... 이런 식으로 탐색을 해야 이전에 탐색을 진행한 수를 체크 여부도 확인하지 않고 넘길 수 있습니다.

이번엔 탐색하는 수의 범위를 고려해보겠습니다. 단순히 2부터 n까지의 수를 직접 비교하는 방법도 있겠지만, 이를 더 최적화할 수 있습니다. 이전 시간에 포스팅을 다룬 기사단원의 무기에서 적용한 방법을 사용할 수 있습니다. 소수는 약수와 연관이 있는 개념이기 때문에 약수의 특징을 이용할 수 있습니다. 약수는 제곱수를 기준으로 서로 매칭되는 특징이 있기 때문에 제곱수보다 큰 수는 체크할 필요가 없습니다. 이를 이 문제에도 적용해본다면 i의 제곱보다 큰 수들에서 걸러지는 배수들은 이미 i의 제곱보다 작은 수들에서 걸러지게 되기 때문에 불필요한 반복만 늘어나게 됩니다. 따라서 범위를 2부터 n/i까지, 즉 i가 2부터 iXi가 n까지 탐색하시면 됩니다.

링크 : https://velog.io/@gale4739/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B8%B0%EC%82%AC%EB%8B%A8%EC%9B%90%EC%9D%98-%EB%AC%B4%EA%B8%B0

아래는 코드입니다.

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isNotPrimeNum = new boolean[n+1];
        
        for(int i=2;i*i<=n;i++){
            if(!isNotPrimeNum[i]){
                for(int j=i*i;j<=n;j+=i) isNotPrimeNum[j] = true;
            }
        }
        
        for(int i=2;i<=n;i++){
            if(!isNotPrimeNum[i]) answer++;
        }
        
        return answer;
    }
}