[Java] BOJ 1978 소수 찾기

문제 

문제 링크 https://www.acmicpc.net/problem/1978

• 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
• 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

아이디어

• 소수 찾기를 보자마자 에라토스테네스의 체가 생각이 났다. (사실 크기가 작아서 하나하나 찾아도 시간초과 안났을 것 같지만 그래도 좀 더 효율적인 방법으로 풀어보고자 에라토스테네스의 체로 풀기로 결심했다. ㅎㅎ)
  
  

겪은 시행착오

• 처음에 문제보자마자 에라토스테네스의 체를 이용하여 풀자라고 생각했지만 막상 사용하려고 보니 원리가 기억이 안나서 조금 고생했다... 앞으로 알고리즘의 이름만 기억하지말고 방법까지 제대로 숙지하도록 공부해야겠다..!

앞으로 에라토스테네스의 체를 이용하여 푸는 문제는 수월하게 풀 수 있도록 확실하게 공부하자!

 

코드

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

// 에라토스테네스의 체를 사용
// 소수들을 대량으로 빠르고 정확하게 구하는 알고리즘

public class BOJ1978 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 범위가 1000이므로
        boolean prime[] = new boolean[1001];

        // boolean 함수가 처음에 false로 초기화 되므로 true가 소수가 아닌 걸로 표시
        // 0과 1은 소수가 아니므로 반대로 바꿔줌
        prime[0] = true;
        prime[1] = true;

        for(int i = 2; i <= Math.sqrt(1000); i++){
            // i가 소수일 경우,
            if(!prime[i]){
                // i의 배수는 소수가 아니므로 boolean 값을 반대로 바꿔줌
                for(int j = i * i; j <= 1000; j = j + i){
                    prime[j] = true;
                }
            }
        }

        int N = Integer.parseInt(br.readLine());
        int cnt = 0;

        // 소수인지 판별할 수 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            int a = Integer.parseInt(st.nextToken());

            // false일 경우, 소수이므로 cnt + 1
            if(!prime[a]){
                cnt = cnt + 1;
            }
        }

        System.out.println(cnt);
    }
}