문제

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

입력

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

출력

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

풀이

2부터 주어지는 수(x)의 제곱근까지 for문을 돌리면서 주어진 수가 나누어지는지 확인하면 된다. 일반적으로 2부터 x-1까지의 수로 x를 나누어보는 경우가 있는데, 이는 엄청난 시간이 소요될 수 있다. 그래서 제곱근을 사용하는 것인데, 예를들어 16이라는 수가 주어졌다고 해보자.

16의 약수는 1, 2, 4, 8, 16이다. 모든 약수에 대해서 가운데 약수를 기준으로 대칭적으로 2개씩 앞뒤로 묶으면 1 x 16, 2 x 8, 4 x 4, 8 x 2, 16 x 1 이렇게 5개의 식이 나온다. 여기서 1 x 16, 16 x 1과 같이 중복되는 식이 존재함을 알 수 있다. 따라서 1, 2, 4에 대해서만 비교해도 뒤에는 비교할 필요가 없어지기 때문에 가운데 약수 즉, x의 제곱근 까지만 해도 되는 것이다.

소스

import java.util.*;

public class Main {
	public static boolean isPrime(int x) {
		if (x == 1) {
			return false;
		}

		for (int i = 2; i <= Math.sqrt(x); i++) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int count = 0;
		for (int i = 0; i < n; i++) {
			int num = sc.nextInt();
			if (isPrime(num)) {
				count += 1;
			}
		}
		System.out.println(count);

	}

}