소수 찾기 (JAVA)

프로그래머스_소수 찾기

처음 풀이

소수는 약수가 1과 자기자신인 수이다. 이 개념을 이용해서 처음 간단하게 문제를 풀었다. 하지만 이론상으로는 맞지만 시간 효율성에서 문제가 생겼었다.
이중 for문을 사용하였는데 만약 n이 1,000이라면 for문은 1,000,000번을 돌아야하므로 효율성에서 문제가 생긴다.

처음 코드 및 결과

public class Solution {
    public int solution(int n){
        int answer = 0;
        int tempAnswer;
        for(int i = 2; i<=n;i++){
            tempAnswer = 0;
            for(int j = 1; j<=i;j++){
                if(i%j==0)
                    tempAnswer ++;
            }
            if(tempAnswer == 2)
                answer++;
        }
        return answer;
    }
}

최종 풀이

시간초과가 난 것을 보니 올해 초 백준에서 비슷한 문제로 고민했던 기억이 났다.

백준_1929
위의 문제도 마찬가지로 실행초과가 났다.

그래서 구글링을 해보니 에라토스테네스의 체를 이용해야 한다고 한다.
해당 수가 소수면 표시를 하고 그 수의 배수들은 모두 소수 후보에서 제외하면 된다.

2차 시도 및 실행 결과

public class Prime {
    public int solution(int n){
        int []arr = new int [n+1];
        for(int i = 0; i<arr.length;i++){
            arr[i] = i;
        }
        int temp = (int) Math.sqrt(n);
        arr[1] = 0;
        for(int i=2; i<=temp; i++) {
            if (arr[i] == 0)
                continue;
            for(int j = i+1;j<=n;j++){
                if(arr[j]==0)
                    continue;

                if(arr[j]%i==0)
                    arr[j]=0;
            }
        }
        int answer = 0;
        for(int i = 0;i< arr.length;i++){
            if(arr[i]!=0)
                answer++;
        }
        return answer;
    }
}

백준에서는 정답이였는데... 여기서는 효율성에서 다시 문제가 생겼다.
그래서 3차 시도...

최종 코드

public class Solution {
     public int solution(int n){
        int []arr = new int [n+1];
        for(int i = 2; i<arr.length;i++){
            arr[i] = 1;
        }
        int temp = (int) Math.sqrt(n);
        
        for(int i=2; i<=temp; i++) {
            if(arr[i]==1){
                for(int j = i;i*j<=n;j++){
                    arr[i*j] = 0;
                }
            }
        }
        int answer = 0;
        for(int i = 0;i< arr.length;i++){
            if(arr[i]!=0)
                answer++;
        }
        return answer;
    }
}

즉 2의 배수들을 다 지우고, 3의 배수들을 다 지우며 소수만 남기고 그 수를 카운트해주면 되는 간단하지만 생각보다 효율성 때문에 힘들었던 문제였다.