[프로그래머스] - 소수찾기 Level1 Java

문제설명

1 ~ n까지의 소수의 개수를 구하여라.

풀이

에라토스테네스의 체
2부터 시작해서 자기 자신이 소수라면 자신의 배수는 소수가 아니다.

3은 소수이므로
6, 9, 12, 15 .... 3의 배수는 소수가 아니다.

5는 소수이므로
10, 15, 20, 25 .... 5의 배수는 소수가 아니다.

Java Code

class Solution {
    public int solution(int n) {
        int answer = 0;
        // 에라토스테네스의 체 역할 
        int[] check = new int[n+1];    
        // 0과 1은 애초에 소수가 아님 배제
        // 초기화 chech의 i번째는 0만 아니도록 초기화해주면 된다.
        for(int i=2;i<n+1;i++) {
            check[i] = 1;
        }
        
        for (int i=2;i<n;i++) {
            // check[i]가 0이라는 것은 해당 i가 소수가 아니라는 의미
            if (check[i] == 0) continue;
            // continue처리가 되지 않고 아래 for문으로 들어왔다는 것은 
            // i가 소수라는 것.
            // i번째를 제외하고 자신의 배수는 모두 소수가 아님 (=check의 자기 배수 번째를 모두 0으로 처리)
            for(int j=i*2; j<=n; j+=i) {
                check[j] = 0;
            }
        }
        // check의 0이 아닌 원소의 수가 소수의 개수
        for (int i=1;i<check.length;i++) {
            if (check[i]!=0) answer++;
        }
        return answer;
    }
}