프로그래머스 LV1) 소수 찾기

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

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

제한 조건

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

 > 에라토스테네스의 체를 활용한 소수찾기 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] sosu = new boolean[n+1]; // 소수 일 때 : false , 소수가 아닐 때 : true
        
        // sosu배열 true로 초기화
        for(int i =2; i <=n ; i++){
            sosu[i] = true;
        }
        
        // 정수 n의 제곱근 구하기
        int root = (int)Math.sqrt(n);
        
        // 2 ~ n의 제곱근까지의 배수를 확인 및 소수false값 입력
        for(int i = 2; i <= root; i++){
            if(sosu[i] == true){
                for(int j = i; i*j<=n; j++){
                    sosu[i*j]= false; 
                }
            }
        }
        // 소수의 개수 값 계산
        for(int i = 2; i <= n; i++){
            if(sosu[i] == true){
                answer++;
            }
        }
        
        return answer;
    }
}

 

 > 정수 n의 제곱근을 기준으로 2 ~ n의 제곱근의 배수를 구해 2 ~ n까지의 수에서 제외를 시켜준다.

 

 

[예시] 1 ~ 100 의 숫자 중 소수 찾기

100 의 제곱근 > 10 

2 ~ 10 까지의 소수 > 2, 3, 5, 7

 1) 2의 배수

 2) 3의 배수

3) 5의 배수

4) 7의 배수

<결과>