[프로그래머스/Lv.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를 반환

 

 

 

✅ 에라토스테네스의 체

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

 

 

 

 

⭕ 풀이

class Solution {
    public int solution(int num) {
        int result = 0;
        boolean[] arr = new boolean[num+1];
		
        for(int i=2;i<=num;i++){
            arr[i] = true;
        }
		
        for(int i=2;i<Math.sqrt(num);i++) {
            if(arr[i]){
                for(int j=i*i;j<=num;j+=i) {
                    arr[j] = false;
                }
            }
        }
		
        for(int i=0;i<=num;i++) {
            if(arr[i]) {
                result++;
            }
        }
		
        return result;
    }
}

 

이전에도 소수찾기관련 문제를 몇번 풀어본적이있는데

그 중 가장 흥미있게 보았던 에라토스테네스의 체 방식을 사용해 풀이해보았다.

 

입력받은수까지의 소수를 찾아야하므로 num에 1을 더한만큼의 길이를 가진 boolean배열을 만든다.

0과 1은 소수가 아니므로 i는 2부터 시작하여 끝까지 true로 초기화해준다.

반복문을 사용하기 귀찮다면 Arrays.fill(arr, true) 로 사용해도 무방하다.

 

이후  i는 2부터시작하고 num의 제곱근까지 i를 증가시키며

arr[i]가 true 즉 아직 false로 초기화되지않은상태( 혹은 소수인상태 ) 라면

j는 i의 제곱부터시작해 j는 i의 배수만큼 늘려가며 arr[j] 를 false로 초기화시킨다

 

ex) 10을 입력받고 2부터 시작하게된다면

arr[i] 즉 2는 아직 true이므로 j는 2*2 4부터 시작해

2씩 늘려가며 false 로 초기화시킨다. 즉 소수가 아니라고 도장을찍는다고 보면된다.

4,6,8,10 이 false 로 초기화되는것이다.

이후 3일경우 9를 false로 초기화시키고

4는 이미 false가 되었기때문에 if문에 걸러져 반복횟수를 줄일 수 있다.

 

이렇게 끝까지 true인채로 살아남은 원소들은 소수라는뜻이므로

마지막 반복문에서 arr[i]가 true라면(소수라면) result++ 를 수행하여 모든 소수의 갯수를 구해 반환한다.

 

 

 

 

 

-출처

https://school.programmers.co.kr/learn/courses/30/lessons/12921