Preparing Coding Test/Baekjoon

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

weero 2021. 2. 15. 21:52

문제

www.acmicpc.net/problem/1978

 

1978번: 소수 찾기

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

www.acmicpc.net

 

전에 정리해뒀던

 

dev2som.tistory.com/27

 

[Java] 소수 찾기

문제 https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자..

dev2som.tistory.com

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

 

설명은 주석으로!

 

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();
	}

}