[알고리즘] 백준 1978번 소수찾기 :: 우유

https://www.acmicpc.net/problem/1978

---

for 문으로 해당되는 숫자까지 무작정 나누어서 0으로 푸는 방법도 있지만,

당연히(?) 비효율적이기 때문에 그렇게 하는 방법보다는

number의 제곱근까지만 나누어주면 되는 방법을 이용하여 풀었다.

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

public class Main {

	static int N;

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

		N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());

		int number = 0;
		int count = 0;

		for (int i = 0; i < N; i++) {
			number = Integer.parseInt(st.nextToken());

			if (number == 1)
				continue;

			boolean flag = true;

			for (int j = 2; j <= Math.sqrt(number); j++) {
				if (number % j == 0) {
					flag = false;
					break;
				}
			}

			if (flag) {
				count++;
			}
		}
		System.out.println(count);

	}

}