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

문제

- 주어진 수 N개 중에서 소수가 몇 개인지 찾기

- N은 100 이하

- 주어지는 N개의 수는 1,000 이하의 자연수

 

해결방법

최근에 소수 구하기 문제를 풀었었기 때문에 빠른 시간 내에 문제를 풀 수 있었다. 

[백준] 1929번 소수 구하기(JAVA)

입력된 수를 소수인지 판단하는 함수로 넘겨서 소수를 판단하고, 소수라면 카운팅을 하여 마지막에 소수의 개수를 출력할 수 있도록 하였다. 이번에도 마찬가지로 효율을 √num 이하의 자연수들로만 num을 나누는 방법으로 구현하여 소요되는 시간을 줄일 수 있도록 하였다.

 

코드

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

class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int count = 0;		// 소수 개수

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<N; i++){
            // 입력을 받으면서 해당 숫자가 소수인지 판별
            if(isPrime(Integer.parseInt(st.nextToken()))) count++;
        }

        System.out.println(count);

        br.close();
    }

    // 소수 판별 함수
    static boolean isPrime(int num){
        if(num <= 1) return false;			// 1은 소수 아님
        else if(num == 2) return true;			// 2는 소수
        else{						// 2부터 sqrt(num)까지 차례로 나누어 봄
            for(int i = 2; i<=Math.sqrt(num); i++){
                if(num % i == 0) return false;
            }
            return true;
        }
    }
}