[Java/백준/소수] 1978번: 소수 찾기

문제

www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

전에 정리해뒀던

 

dev2som.tistory.com/27

[Java] 소수 찾기

의 에라토스테네스 체 방법을 참고했다.

 

설명은 주석으로!

 

package boj;

import java.io.*;

public class BOJ1978 {
	static boolean[] isComposite;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n];

		int max = 0;
		String[] inputs = br.readLine().split("\\s");
		for (int i = 0; i < n; i++) {
			input[i] = Integer.parseInt(inputs[i]);
			max = Math.max(max, input[i]);
		}

		isComposite = new boolean[max + 1];

		isComposite[1] = true;
		for (int i = 2; i * i <= max; i++) {
			if (isComposite[i])
				continue;
			for (int j = i + i; j <= max; j += i) {
				isComposite[j] = true;
			}
		}

		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (!isComposite[input[i]]) {
				++cnt;
			}
		}

		System.out.println(cnt);

		br.close();
	}

}