문제

백준 1979번
https://www.acmicpc.net/problem/1979

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

주어진 수들 중 소수의 개수를 출력한다.

Code

• [백준_1929] 소수 구하기와 유사한 문제(해설)

  • https://velog.io/@kmh9250/%EB%B0%B1%EC%A4%801929-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

Java

import java.util.*;
import java.io.*;

public class Main {
    static boolean[] isCheck;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());  // 수의 개수
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];  // 입력된 수의 배열
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        isCheck = new boolean[1001];  // 조건 : 최대 1000 이하의 자연수
        primeCheck();  // 소수 확인 메서드
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            // false 이면 소수이므로 count를 늘려준다.
            if (!isCheck[arr[i]]) {
                count++;
            }
        }
        System.out.println(count);
    }

    public static void primeCheck() {
        isCheck[0] = true;
        isCheck[1] = true;
        for (int i = 2; i < Math.sqrt(isCheck.length); i++) {
            // 소수가 아닌 경우
            if (isCheck[i]) {
                continue;
            }
            for (int j = i * i; j < isCheck.length; j += i) {
                isCheck[j] = true;
            }
        }
    }
}