프로그래머스)level.1_소수 찾기(에라토스테네스의 체)

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

< 나의 풀이 1 - 효율성 테스트 실패 >

public int solution(int n) { int answer = 0; for (int i = 2; i <= n; i++) { Loop1: for (int j = 2; j <= i; j++) { if (i % j == 0 && j != i) { break Loop1; // 소수가 아닌경우 } else if (i % j == 0 && j == i) answer++; } } System.out.println(answer); return answer; }

이 문제의 포인트는 '효율성'이다.

1,000,000 까지의 수를 일일이 나눠보는 비효율적인 코드로는 통과할 수가 없는데, 위의 코드가 그렇다. 

이 코드로는 정확성 테스트 10까지 밖에 통과할 수 없고 11,12는 시간초과가 뜨며 효율성 테스트에서는 모두 낙제했다.

 

소수를 찾아내는 코드는 시간의 효율성을 배제하고서 조금만 생각 한다면 어렵지 않게 짜낼 수 있겠지만

그렇지 않다면 (적어도 나는)굉장히 골아픈 문제였다.

 

그래서 서치해보니 '에라토스테네스의 체'를 이용하여 상당히 효율적인 코드를 구현해 낼 수 있는데

(* 에라토스테네스의 체 : 간단히 말하면 1이아닌 '어떤 수'의 n배가 되는 수는 소수가 될 수 없으므로 '어떤 수'의 n배가 되는 수들을 계속해서 pool에서 빼내는 방법)

이론은 심플하여 이해가 가더라도 막상 코딩하려니 굉장히 어려웠고 하여 이사람 저사람 코드를 참고하여 아래와 같이 작성했다.

 

 

< 나의 풀이 2 - 에라토스테네스의 체 >

public int solution(int n) { boolean[] arr = new boolean[n + 1]; for (int i = 2; i <= n; i++) { if (arr[i]) continue; for (int j = i + i; j <= n; j += i) { arr[j] = true; } } int answer = 0; for (int i = 0; i < arr.length; i++) { if (!arr[i]) { answer++; } } return answer - 2; }

boolean[] arr = new boolean[n + 1];

n+1크기의 boolean형 배열을 선언. (0부터 n까지 들어가야 하기 때문)

초기값은 false이고 여기서 소수가 아닌 수들을 true로 체크 할것이다.

 

for (int i = 2; i <= n; i++) {
if (arr[i])
continue;

arr[i]가 true일때 continue를 만나 아래 j for문이 실행되지 않고 i++가 된다.

i는 2부터시작 하여 0과1은 false인 채로 있기 때문에 마지막 return값에 -2를 했다.

2부터 시작해보면 2는 일단 초기값 false이니 아래 for문이 실행된다.

for (int j = i + i; j <= n; j += i) {
arr[j] = true;
}

j는 4부터 시작, j<=n까지 j에 i값을 누적하는 식이다.

여기서 arr[4](=4. 소수가 아님)는 true로 바뀌고 그다음 j는 6->8->10 ....순으로 2의 배수를 모두 false로 바꾼 후

n까지 도달하게 되면 그 다음 i값 3. 3은 이전 순서에서 true로 바뀌지 않았으니 또 j for문을 돌아 이번엔 3의 배수가 true로 바뀌게 될 것이다. 그 다음 i값은 4. 4는 i값이 2일때 j for문 안에서 true로 바뀌었으므로 j for문이 실행되지 않고 i++가 된다.

이런식으로 반복문의 실행을 최소화 하여 효율성을 높이는 코드.

 

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

최종적으로 arr안의 false값을 찾아 answer을 증가시켜주고 최종 return은 -2를 하여 0과 1의 갯수를 빼준다.

 

더 효율적인 방법이 있겠지만 이건 더이상 그만 보고 싶다.

으앙