[Java]백준 1978번 :: 소수 찾기

백준 온라인 저지 1978번 '소수 찾기'

Java 알고리즘 문제풀이

풀이

소수찾기 문제이다. 

이 문제는 입력한 숫자가 소수인지를 판단하는데 각각의 수가 소수인지 판단을 하고 소수이면 count값을 증가시키면 된다. 

소수의 특징은 1과 자신만을 약수로 가진다는 점이다. 간단하게 풀 수 있는데 

입력받은 숫자가 만약에 자신의 수 이외에 나머지 값을 0으로 가진다면 소수가 아니다. 이 점을 이용하면 된다.

이런 부류의 문제의 심화버전은 에라토스테네스의 체 알고리즘을 이용해야한다.

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

public class Beak1978 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(arr[i], max);
        }

        boolean[] check = new boolean[max + 1];

        check[0] = check[1] = true;

        for (int i = 2; i * i <= max; i++) {
            for (int j = i * i; j <= max; j += i) {
                check[j] = true;
            }
        }

        int cnt = 0;
        for (int a : arr) {
            if (!check[a])
                cnt++;
        }
        System.out.println(cnt);
    }
}