백준 1978번: 소수 찾기

문제 출처: https://www.acmicpc.net/problem/1978

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        String[] arr = reader.readLine().split(" ");
        int result = 0;
        
        for(int i=0 ; i<N ; i++){
            int num = Integer.parseInt(arr[i]);
            // 자연수 num의 소수 판별
            // 기본 원리:2부터 num-1의 수로 나눌 때, 나눠지는 수가 있으면 소수가 아님
            // 더 나아가서: 2부터 sqrt(num)의 수로 나눌 때, 나눠지는 수가 있으면 소수가 아님
            // -> '나누는 수'와 '몫' 중 하나는 반드시 sqrt(num)이하이기 때문
            if(num == 1)
                continue;
            
            boolean isPrime = true;
            for(int j=2; j<=(int)Math.sqrt(num) ; j++){
                if(num%j == 0){
                    isPrime = false;
                    break;
                }
            }
            
            if(isPrime)
                result++;
        }
        
        System.out.println(result);
    }
}