[백준 1978] 소수찾기 (자바)

백준 1978번: 소수 찾기 (2트)

문제 설명

주어진 N개의 수 중에서 소수의 개수를 찾아 출력하는 문제입니다. 소수란 1과 자기 자신만을 약수로 가지는 수를 의미합니다.

문제 접근 방법

1. 입력받은 수가 1이면 소수가 아니므로 건너뜁니다.
2. 입력받은 수가 소수인지 판단하기 위해 2부터 해당 수의 바로 앞까지의 수로 나눠봅니다.
3. 나누어 떨어지는 수가 없으면 소수로 간주하고 개수를 셉니다.

시간 복잡도 분석

O(N * M)

• N은 입력받은 수의 개수입니다.
• M은 각 수의 최대 크기입니다. 최악의 경우 N개의 수가 모두 최대 크기일 때, M번의 나눗셈을 수행해야 합니다.
• 따라서 시간 복잡도는 O(N * M)입니다. 이는 입력받는 수의 범위가 작다면 효율적입니다.

해결 방법

아래는 주어진 수들 중 소수를 찾는 Java 코드입니다:

package re_02;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1978_소수찾기_2트 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(st.nextToken());
            if (input == 1) {
                continue;
            }
            boolean isPrime = true;
            for (int j = 2; j < input; j++) {
                if (input % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}