[백준 자바] 1978번(소수 찾기)

난이도 - 브론즈 2

문제

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

입력

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

출력

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

 

---

 

728x90

5이상의 모슨 소수는 6의 배수 +- 1의 형태이다. (5와 7, 11과 13, 17과 19, ...) 이를 소수 판별 알고리즘에 적용한다.

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

public class Main1978 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int count = 0;
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		while (N-- > 0) {
			int num = Integer.parseInt(st.nextToken());
			if (isPrime(num))
				count++;
		}
		bw.write(String.valueOf(count));

		bw.flush();
		br.close();
		bw.close();
	}

	static boolean isPrime(int n) {
		if (n == 1)
			return false;
		else if (n <= 3)
			return true;
		else if (n % 2 == 0 || n % 3 == 0)
			return false;

		for (int i = 5; i * i <= n; i += 6) {
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		}
		return true;
	}
}