[12921] 소수 찾기

✔ 소수 찾기

[프로그래머스 12921]

문제 분석하기

에라토스테네스 방법으로 문제를 풀이

손으로 풀어보기

1. 첫 번째 인덱스가 0인 것을 고려하여 크기가 n + 1인 배열을 선언한 후 값은 각각의 인덱스값으로 채움
2. 1은 소수가 아니므로 삭제
3. 2부터 n의 제곱근까지 값을 탐색하며 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경
4. 배열에 남아 있는 수 중 소수인 값의 개수를 세어 반환

슈도코드 작성하기

n(숫자)
answer(소수의 개수)
arr(소수 배열)
for(n만큼 반복하기) {
    arr 배열 초기화하기
}
for(n의 제곱근까지 반복하기) {
    이미 소수가 아니면 넘어감
    for(소수의 배수 값을 n까지 반복하기) {
        이 수가 소수가 아니라는 것을 표시하기
    }
}
for(1 ~ n까지 반복하기) {
    arr 배열에서 소수인 경우 answer 증가
}
answer 반환

코드 구현하기

/**
 * 12921) 소수_찾기
 */
public class L012_12921 {
    // n(숫자)
    public int solution(int n) {
        // answer(소수의 개수)
        int answer = 0;
        // arr(소수 배열)
        int[] arr = new int[n + 1];
        // arr 배열 초기화하기 (자기 자신의 값으로 채우기)
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
        // n의 제곱근까지 반복하기
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // 이미 소수가 아니면 넘어감
            if (arr[i] == 0)
                continue;
            // 소수의 배수 값을 n까지 반복하기
            for (int j = i + i; j <= n; j = j + i)
                // 이 수가 소수가 아니라는 것을 표시하기
                arr[j] = 0;
        }
        // 1 ~ n까지 반복하기
        for (int i = 1; i <= n; i++) {
            // arr 배열에서 소수인 경우 answer 증가
            if (arr[i] != 0)
                answer++;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L012_12921 solution = new L012_12921();

        int n = 10;

        int result = solution.solution(n);

        System.out.println(result);
    }
}