[인프런] 소수 구하기(에라토스테네스의 체)

소수 구하기(에라토스테네스의 체)

소수를 판별하는 알고리즘

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성

 

■ 문제 풀이

1) 입력 설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어진다.

2) 출력 설명
소수의 개수를 출력한다.

3) 테스트
- input : 20
- output : 8

4) 문제 풀이
- 에라토스테네스의 체를 사용
- 소수를 판별할 범위만큼 배열을 할당, 초기 값으로 0을 설정
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 지운다.
- 모두 지우고 남은 수가 소수가 된다.

[참고]
- 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

 

import java.util.Scanner;

public class Main {

    private int solution(int input) {
        int answer = 0;
        int[] check = new int[input + 1];

        for (int i = 2; i <= input; i++) {
            if (check[i] == 0) {
                answer++;
                for (int j = i; j <= input; j = j + i) {
                    check[j] = 1;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();

        System.out.println(main.solution(input));
    }
}