[백준] 1978

소수 판별
소수는 1과 자기자신을 제외하고 나누어지지 않는 경우를 말한다.
즉, 약수가 1과 자기자신 말고는 없어야 한다.
이런 성질을 사용해서, 약수와 마찬가지로 절반만 살펴본다.
절반을 봐도 1제외 약수가 없다면 그것은 소수인 셈이다.

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

public class Main {

    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());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int count=0;

        for(int i=0;i<N;i++) {
            int num = Integer.parseInt(st.nextToken());
            if(isPrime(num)) count++;
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isPrime(int n) {
        if(n < 2) return false;
        for(int i=2; i*i<=n; i++) {
            if(n%i==0) return false;
        }
        return true;
    }
}