[프로그래머스] 소수(Prime number) 찾기

처음 풀어본 알고리즘 (?) 문제..였다. "소수"라는 말도 오랜만에 들어봄. 

운이 좋게 코테 스터디를 시작했는데, 같이 공부하는 스터디원분이 열심히 정리하여 설명해 주셨다.

설명을 기준으로 정리를 해보겠다!

 

나는 소수를 뽑아내서 그것들을 배열에다 집어넣고, 이미 소수로 선정된 수들은 제외(?) 해야 하나...? 

아 머리가 안 돌아가... 난 역시 바본가...

이러고 있었는데

 

일단 힌트를 받고 풀어보았다. 

 

1️⃣차 시도

class Solution {
    public int solution(int n) {
        int answer = 0; 
        
        // 2부터 n까지 소수체크하는 반복문 생성
        for (int i=2; i<=n; i++) {
        	// 소수체크를 하는 불리언 변수선언
        	boolean sosuCheck = true;
            for (int j=2; j<i; j++) { //2부터 i값까지 확인할 것 
				if (i%j==0) { // i를 j로 나눴을 때 나머지가 없다면 소수가 아님
                	sosuCheck = false; // 소수체크 불리언을 false로 두고 for문 탈출
                    break;
                }
                if(sosuCheck) answer++; // 소수체크 불리언이 true면 answer숫자 올리기
            }
        } return answer;
    }
}

일단 코드 실행 돌려보는 것은 성공.. 그러나 제출을 하니 시간 초과로 인한 실패가 나왔다. 

즉 효율성이 우우~😵‍💫라는 뜻 

왜냐하면 모든 경우의 수마다 소수인지 아닌지 판별하는 것이 무의미하기 때문이다. >> 그래서 확인하는 범위를 줄여보자!! 라는 결론이 나옴.

 

그렇다면

2️⃣차 시도 !

팁은 확인 범위를 제곱근으로 줄여보자...

 

소수라면 1과 자기 자신으로만 나누어지지만, 소수가 아니라면 무조건 axb의 곱으로 나타낼 수 있다.

예를 들어, 6은 1x6, 2x3 이러한 형식으로 나타낼 수 있는데, a와 b중 하나는 무조건 n의 제곱근보다는 작다는 것을 알 수 있다!! 

그러므로 확인을 n의 제곱근까지만!! 확인해보면 되지 않나~~~~~ 라는 생각을 해보았다.

제곱근을 계산한다면 정수가 나오지 않으므로 거기다가 int로 형변환을 시켜준다. 

>> 6은 그럼 2,3,4,5까지 확인절차를 거치다가 >> 2만 확인해보아도 결과를 알 수 있다는 것이다!!

이 때 주의할 점은 int값으로 변경하면서 <=등호를 추가! 해야 한다는 것. 제곱근 값과 같아도 확인절차가 필요하므로.

 

코드로 만들어보면 요렇게 나옵니다 하나만 바꾸면 됨!

class Solution {
    public int solution(int n) {
        int answer = 0; 
        
        // 2부터 n까지 소수체크하는 반복문 생성
        for (int i=2; i<=n; i++) {
        	// 소수체크를 하는 불리언 변수선언
        	boolean sosuCheck = true;
            //2부터 i값까지가 아니라, i의 제곱근값까지만 확인할 것 
            for (int j=2; j<=(int)(Math.sqrt(i)); j++) { 
            	if (i%j==0) { // i를 j로 나눴을 때 나머지가 없다면 소수가 아님
               		sosuCheck = false; // 소수체크 불리언을 false로 두고 for문 탈출
                    break;
                }
                if(sosuCheck) answer++; // 소수체크 불리언이 true면 answer숫자 올리기
            }
        } return answer;
    }
}

>> 짠 실행을 해보니 모두 통과 정답 인정!! 

요렇게 만족해도 되지만

 

이름부터 어려운 "어쩌구저쩌구체"를 활용해보기로 했다...

어쩌구저쩌구체 = 에라토스테네스의 체입니다..

 

3️⃣차시도! 

에라토스테네스의 체 활용하기

 

>> 이것은 소수라고 판정된 수의 배수들을 모두 제거함으로써 소수를 빠르게 찾아내는 방법이라고 한다!

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

이 설명사진을 보면 정말 체처럼 소수가 아닌 수들이 모두 걸러져... 소수만 남게 된다! 

>> 자 이걸 코드로 짜보는 것이 제일 중요하다!! 

 

class Solution {
    public int solution(int n) {
       // 소수체크하는 불리언 배열 만들기 (크기는 n+1)
        boolean[] primeCheck = new boolean[n+1];
        int answer = 0;

        // 소수체크 배열의 기본값은 false이지만,
        // 배열[0], [1]을 제외한 나머지 값들을 소수라고 가정하고 true로 만들기
        for (int i=2; i<=n; i++) {
            primeCheck[i] = true;
        }

        // 반복문 만들어서 소수의 배수들을 false로 만들기
        // 2부터 n의 제곱근까지 소수인지 판별하기
        // (Math.sqrt()대신 i*i<=n 으로 설정)
        for (int i=2; i*i <=n; i++) {
            // 소수판별하여 true일 때 조건문 들어가기 
            if (primeCheck[i]) { 
                // 조건문 내에서는 j가 2부터 n까지 j+=i(i의 배수)를 false로 만들기
                for (int j=i*2; j<=n; j+=i) {
                    primeCheck[j] = false;
                }
            }
        }

        // 소수체크 배열이 참일 때 answer 하나씩 올리기
        for (int i=2; i<=n; i++) {
            if (primeCheck[i]) answer++;
        }
  
        return answer;
    }
}

** 포인트

1) boolean을 배열로 만들기 

2) 불리언 배열의 크기는 ? n+1이다 (이유는 배열은 인덱스가 0부터 시작하기 때문>> 0과 1은 제외하자)

3) 소수인 배열 인덱스를 true로 만들고 소수가 아닌 수를 false로 만들어서 true만 세기.

4) 범위값은 제곱근 이하로 설정하기 (Math.sqrt() 대신에 i*i<=n으로 설정함)

 

 

왼: 2차시도(범위값 조정)                                                 오: 3차시도(범위값 조정+에라토스테네스의 체 사용)

요렇게 실행해보면 시간 차이가 명확!!!!!하다.

에라토스테네스의 체가 확실히 소수의 개수를 구할 때에 너무 유리한 방법인 것 같다.