JAVA백준 문제풀이 (8) 1978:소수 찾기

 

 

 

에라토스테네스의 체를 활용하면 쉽게 풀 수 있는 문제이다.

예전에 포스팅한 적이 있으니 잘 모르면 읽어보도록 하자.

 

https://7357.tistory.com/104

0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체

 

 

에라토스테네스의 체는 굉장히 심플해서 한 번 보면 바로 이해가 되는데, 문제는 이걸 어떻게 코드로 작성하지? 라고 생각하면 또 벙찌게 될 수도 있다.

그러면 그냥 여러번 풀어보면 된다.. 그것이 수학이니까.. ㅋㅋㅋ ㅜ

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        boolean[] booleans = new boolean[1000+1];
        // 입력 범위가 0~999가 아닌 1~1000이므로 인덱스 +1
        booleans[0] = booleans[1] = true;
        // 아래의 방법으로 0,1은 소수가 아닌 수로 지정해줄 수 없기 때문에 수동으로 값을 넣어줘야 한다.

        for ( int i=0; i*i< booleans.length; i++) {
            if (!booleans[i]) {
            // 일단 모든 수를 false로 두고 어떤 수의 배수면 제외하는 것이다
                for (int j = i * i; j < booleans.length; j += i) {
                    booleans[j] = true;
                }
            }
        }

        int result = 0;
        for ( int i=0; i<T; i++ ) {
            if (!booleans[Integer.parseInt(scanner.next())]) {
                result += 1;
            }
        }
        System.out.println(result);
    }
}