[백준 알고리즘] 1978 - 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

이 문제는 에라토스테네스의 체를 사용하여 문제를 해결할 수 있습니다.

 

에라토스테네스의 체란 앞에서부터 자기 자신의 배수들을 하나씩 제거하는 방식으로 소수를 찾는 방식입니다.

 

사진 출처 - 위키백과

자바 코드는 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
         // 소수인 경우 true, 아니면 false
         boolean[] nums = new boolean[1001];
        Arrays.fill(nums, true);
        nums[0] = false; nums[1] = false;

         // 에라토스테네스의 체 방식으로 소수가 아닌 경우를 찾아 false로 변경
         for (int i = 2; i < nums.length - 1; i++) {
             for (int j = i + 1; j < nums.length; j++) {
                 // 이미 소수가 아닌 경우(false)는 다시 확인하지 않음
                 if (nums[j]) {
                     nums[j] = j % i != 0;
                 }
             }
         }

        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int t = Integer.parseInt(br.readLine());
         int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

         int answer = 0;
         for (int i = 0; i < t; i++) {
             // 해당 숫자가 소수인 경우(true)
             if (nums[input[i]]) {
                 answer++;
             }
         }

         System.out.println(answer);
    }
}