[프로그래머스] 소수 찾기 (JAVA)

문제 출처 - Programmers

문제는 여기

---

[풀이]

1. 에라토스테네스의 체를 사용해준다.

Arrays.fill(prime, true);
prime[0] = prime[1] = false;
		
for (int i = 2; i * i < prime.length; i++) {
    if (prime[i]) {
        for (int j = i * i; j < prime.length; j += i) {
            prime[j] = false;
        }
    }
}

2. 1부터 범위까지 소수의 개수를 구해준다.

3. 결과를 출력한다.

[접근]

1. 에라토스테네스의 체를 사용해주고 1부터 범위까지의 소수를 구해주면 되겠다고 생각하였다.

[코드]

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] prime = new boolean[n + 1];
        
        // 에라토스테네스 체 사용
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
		
        for (int i = 2; i * i < prime.length; i++) {
            if (prime[i]) {
                for (int j = i * i; j < prime.length; j += i) {
                    prime[j] = false;
                }
            }
        }
        
        // 소수의 개수 세기
        for (int i = 1; i < prime.length; i++) {
			if (prime[i]) {
				answer++;
			}
		}
        
        return answer;
    }
}