[1978] 소수 찾기 (JAVA)

# 문제 설명

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

---

입력

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

---

출력

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

 

# 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //숫자의 개수
        int[] inputNum = new int[N];

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

        int[] numbers = new int[max+1];
        for (int i = 2; i <= max; i++) {
            numbers[i] = i;
        }

        for (int i = 2; i < numbers.length; i++) {
            if (numbers[i] > 0) {
                for (int j = i + 1; j < numbers.length; j++) {
                    if (numbers[j] > 0 && j % i == 0) {
                        numbers[j] = 0;
                    }
                }
            }
        }

        int cnt = 0;
        for (int i : inputNum) {
            if (numbers[i] != 0) {
                cnt++;
            }
        }

        System.out.print(cnt);
    }
}

 

숫자의 개수 N을 입력 받고 N개의 숫자를 inputNum 배열에 저장한다.

숫자를 입력 받으면서 최댓값을 찾아 max에 저장한다.

 

2부터 max까지 숫자를 저장할 배열 numbers를 만든다.

1은 소수가 아니므로 2부터 저장한다.

또한 인덱스와 값을 같게 쓰기 위해 배열 크기를 max+1로 설정한다.

 

numbers를 순회하면서 현재 i가 제거된 값이 아니라면(0이 아니면), i의 배수를 제거한다.

위 과정을 거쳐 numbers에는 소수가 아닌 수는 제거된다.

 

입력 받은 숫자 배열을 순회하면서 numbers 배열에서 제거되지 않은 수이면 cnt를 1 증가한다.