문제링크

풀이

많이 익숙한 소수를 구하는 문제이다.

소수

소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 말한다. 이러한 소수를 구하기 위해 가장 간단한 방법은 입력값 n보다 작은 수로 일일히 나눠보는 것이다. 이 때 이 나누는 값의 범위를 $\sqrt{n}$ 까지로 제한하여 더 빨리 찾을 수 있다.

n의 제곱근까지 확인

자연수 $n$에 대하여 $a \times b$, $m \times m (m = \sqrt{n})$으로 표현될 때, $a \times b = m \times m$이라고 할 수 있다. ($a, b, m$은 모두 자연수)

이 때 $a, b$가 자연수가 되기 위해서는 아래 조건 중 하나를 충족해야 한다.
1) $a = m, b = m$
2) $a > m, b < m$
3) $a < m, b > m$

따라서 $a$와 $b$ 둘 중 하나는 m보다 작거나 같아야 한다($a \leq m$ or $b \leq m$). 즉, 자연수 $n$이 소수인지 판별하기 위해서는 1보다 크고 $\sqrt{n}$보다 작거나 같은 자연수들만 확인하면 된다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int prime_num = 0;
        for (int i = 0; i < n; i++) {
            int value = Integer.parseInt(st.nextToken());

            if (value == 1) {
                continue;
            }

            if (isPrime(value)) {
                prime_num++;
            }
        }

        System.out.println(prime_num);
    }

    public static boolean isPrime(int num) {
    	if (num == 1) {
            return false;
        }
        
        for (int divisor = 2; divisor <= Math.sqrt(num); divisor++) {
            if (num % divisor == 0) {
                return false;
            }
        }

        return true;
    }
}

참고링크

에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유