[백준] 1978번 소수 찾기 (JAVA)

방법1. 일반적인 식

• 1, 본인 제외 한 수로 나눈 나머지가 모두 0이 아닌 경우

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() ) {
            int num = Integer.parseInt(st.nextToken());
            if( num == 1 ) continue;

            boolean isPrime = true;
            for(int j=2; j<num; j++) {
                if( num % j == 0 ) {
                    isPrime = false;
                    break;
                }
            }
            if( isPrime ) {
                cnt++;
            }

        }
        System.out.println(cnt);
    }
}

방법2. 알고리즘 ‘에라토스테네스의 체’ 이용

[참고]
https://velog.io/@dayoung_sarah/알고리즘-에라토스테네의-체

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();	// 주어진 수는 사용하지 않는다.

        // 입력값 범위는 1000이하의 자연수
        boolean[] primeArray = getPrimeArray(1000);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int cnt = 0;
        while( st.hasMoreTokens() ) {
            int num = Integer.parseInt(st.nextToken());
            if( !primeArray[num] ) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static boolean[] getPrimeArray(int max) {
        boolean[] primeArray = new boolean[max+1];
        primeArray[0] = true;
        primeArray[1] = true;

        for(int i=2; i<=Math.sqrt(max); i++) {
            if( primeArray[i] ) continue;

            for(int j=i*i; j<primeArray.length; j += i) {
                primeArray[j] = true;
            }
        }

        return primeArray;
    }
}