JAVA 백준 1978번 소수 찾기

문제

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

입력

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

4
1 3 5 7

출력

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

3

알고리즘 분류

수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve)

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer token = new StringTokenizer(br.readLine());
        int[] num = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(token.nextToken());
            if (num[i] > max) max = num[i];
        }
        boolean[] nprime = new boolean[max + 1];
        nprime[0] = true;
        nprime[1] = true;
        double sqrtmax = Math.sqrt(max);
        for (int i = 2; i <= sqrtmax; i++) {
            for (int j = i + i; j <= max; j += i) {
                if (nprime[j] == false)
                    nprime[j] = true;
            }
        }
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (nprime[num[i]] == false) count++;
        }
        System.out.println(count);
    }
}