소수 찾기

코딩테스트 문제에 간간히 나오며, 소수인지를 판별하기 가장 쉬운 방법이다
'에라토스테네스의 체' 라고도 하는데 쓰는 방법은 간단하다.

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

		int cnt = 0;
		while(st.hasMoreTokens()) {
            boolean b = true;
            //정수 x에 대하여 소수를 판별한다 
			int x = Integer.parseInt(st.nextToken());
            
            // 먼저 0,1은 소수가 될 수 없다.
			if(x == 0 || x == 1 ) {
				 continue;
			}

			//2~n의 제곱근까지 돌면서 나누어 떨어진 값이 0이면 소수가 아니다
			for (int j=2;j<=Math.sqrt(x);j++) {
				if(x % j == 0) {
					// 소수 아닐 경우 false;
					b = false;
				}
			}
			
            // boolean을 이용해 소수가 맞는지 판단 할 수 있다.
			if(b) {
            	// 소수일 경우 cnt 증가
				cnt++;
			}

		}
		
		System.out.print(cnt);



	}

}