[프로그래머스_Level1] 소수 찾기

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

코딩테스트 연습 - 소수 찾기

[문제]

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

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

 

[제한 조건]

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

 

[코드]

class Solution {
public int solution(int n) {
        int answer=0;
        boolean[] sosu=new boolean[n+1];
        sosu[0]=sosu[1]=true; // 0과 1은 소수가 아니기 때문에 true 처리
        
        /* 
         * <에라토스테네스 알고리즘>
         * 2부터 루트n 이하까지 반복하여
         * 자연수중에서 k를 제외한 k의 배수들을 제외시켜가며 소수를 구하는 알고리즘
         */
        for(int i=2;i<n;i++) {
        	// 이미 체크된 배열이라면 넘어간다.
        	if(sosu[i]==true)
        		continue;
        	// i의 배수들을 걸러주기 위한 반복문
        	for(int j=i+i;j<=n;j=j+i)
        		sosu[j]=true;
        }
        
        /* 
         * boolean 배열의 값이 false인 인덱스 값은 소수이기 때문에 
         * false 값을 가지는 배열의 갯수 카운트
         */
        for(int i=2;i<=n;i++)
        	if(sosu[i]==false)
        		answer+=1;
        
        return answer;
    }
}

[고찰]

 이번 문제는 소수를 구하는 대표적인 방법인 에라토스테네스의 채 방법을 사용하여 해결하였다. 소수를 수하는 알고리즘 하나 정도는 암기하고 있는 것이 좋기 때문에 해당 알고리즘은 여러번 복습해야겠다고 생각한다.

<에라토스테네스의 채> 소수를 구하는 대표적인 방법 중 하나로 'k=2부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시켜가며' 소수를 구한다. 출처 : https://st-lab.tistory.com/81