[백준 BOJ][JAVA] 1978번: 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

문제 풀이(코드)

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        int max = 1000;
        
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scan.nextInt();
        }
        
        // 소수면 false, 소수가 아니면 true
        boolean[] checked = new boolean[max + 1];
        checked[0] = checked[1] = true;
        for (int i = 2; i < Math.sqrt(max); i++) {
            if (!checked[i]) { // checked[i]가 false일 때 = 소수일 때
                for(int j = i * i; j <= max; j += i) {
                    checked[j] = true; // checked[j]는 소수가 아님
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!checked[array[i]]) { // checked가 false = 소수
                count++;
            }
        }
        System.out.println(count);
        
        scan.close();
    }
}