[프로그래머스] 소수 찾기 (lv.1)

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

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

 

[문제 풀이]

 

1. 에라토스테네스의 체를 이용하여 소수를 구한다.

  1-1. 소수를 판별하는 배열을 만든다.

  1-2. 0과 1은 소수가 아니므로 false를 넣고, 나머지를 true로 채운다.

  1-3. 소수이면 해당 숫자의 배수를 모두 false(소수가 아니면 제거)로 바꾼다.

2. 소수가 몇 개인지 구한다.

 

출처 : https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

[소스 코드]

 

import java.util.Arrays;

public class FindPrimeNumbers {
    public static void main(String[] args) {
        int n = 12;

        System.out.println(solution(n));
    }

    private static int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n + 1];

        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * 2; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 0; i <= n; i++) {
            if (isPrime[i]) {
                answer++;
            }
        }

        return answer;
    }
}