백준 소수 찾기 1978

문제

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

시간 제한 2s

입력

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

출력

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

예제입력

4 1 3 5 7

예제출력

3

풀이

1. 1은 소수가 아니다.
2. 2부터 N까지 나눠서 나머지가 0이 안나오면 소수로 인정 하지만 시간복잡도는 O(N)
3. 제곱근을 이용한 방법 (합성수)
4. 합성수 n = a * b 에서 a,b 중 적어도 하나는 n의 제곱근보다 작거나 같다.
5. 자바 제곱근 Math.sqrt() 함수 이용

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 bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        int primeNumCount = 0;
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        while (stringTokenizer.hasMoreTokens()){
            if(isPrimeNum(Integer.parseInt(stringTokenizer.nextToken()))){
                primeNumCount++;
            }
        }
        System.out.println(primeNumCount);
    }

    static boolean isPrimeNum(int num){
        if (num == 1){
            return false;
        }

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

}