[알고리즘] 소수 찾기 (에라토스테네스의 체)

알고리즘... 너무 어렵다ㅠㅠ 이전에 수학을 잘했다고 좋아했다며 알고리즘은 재밌고 자신있다고 자만했던 내 자신이 너무 부끄럽다...

문제가 막힐 때마다 좌절감과 현타가 오지만, 나 외에도 모두가 어려워한다는 자기 위로를 하며 다시 한번 마음을 잡아본다.

오늘 풀었던 문제 중 프로그래머스 '소수 찾기'(level 1) 문제를 리뷰하며 복기해보자.

오? 소수? 괜찮은데? 하면서 아무 생각없이 풀어보았다.

[첫번째 도전]

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

오.. 껌인데?! 하며 코드 실행 후 제출했는데 이런... 효율성? 에서 시간초과로 실패했다...
아니, 도대체 뭐야?? 내가 모르는 패키지나 함수가 있나?
열심히 머리를 굴리고 다시 시도해봤다.

[두번째 도전]

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

그래, 짝수는 어차피 2의 배수이기에 2를 제외한 짝수는 모두 소수니까 빼자.
그러면 시간도 줄고 효율성도 나아질거야!

또 실패...

더 머리를 굴리기엔 나오는 답이 없어 검색을 했고 알게된 이름도 어려운 "에라토스테네스의 체"
소수를 찾는 빠르고 쉬운 방법이란다. 난생 처음 들어보았다...

이 방법으로 본 문제를 푸는 순서는 다음과 같다.

1. 2부터 문제의 n까지 모든 수를 나열한다.
2. 2부터 n까지 반복하여 자기 자신을 제외한 배수를 제거한다.
3. 제거되지 않은 숫자의 개수를 구한다.

[통과한 답]

class Solution {
    public int solution(int n) {
        
        if(n == 2) return 1; // n이 2일때는 소수는 2로 답은 1개이다.
        
        int[] arr = new int[n+1]; 
        
        for(int i=2; i<n+1; i++){ // 2부터 n까지 나열한 배열을 만든다.
            arr[i] = i;
        }
        
        for(int i=2; i<n+1; i++){
            if(arr[i] != 0){
                for(int j=i+i; j<n+1; j+=i){ // 자기 자신을 제외한 배수를 제거한다. (값을 0으로 변경) 
                    arr[j] = 0;   
                }
            }
        }
        int answer = 0;
        for(int i=2; i<n+1; i++){ // 값이 0이 아니면 answer를 1씩 증가시킨다.
            if(arr[i] != 0) answer++;     
        }

    return answer;
    
    }
}

쉬운 문제인줄 알고 덜컥 덤볐다가 호되게 당하고 다시금 겸손해졌다.ㅎㅎ
하나 더 배웠다! 뿌듯뿌듯

본 포스팅은 멀티캠퍼스의 멀티잇 백엔드 개발(Java)의 교육을 수강하고 작성되었습니다.