[백준 JAVA] 1978 - 소수 찾기

기본적인 소수 찾기 문제이다!

 

매우 쉬운 문제이며 필자는 예전에 소수문제를 에라토스테네스의 체를 공부해서 푼 기억이 난다.

이참에 다시 복습할 겸, 간단한 문제여도 해당 알고리즘을 사용하기로 결심했다!

 

에라토스테네스의 체는 시간복잡도가 O(n * log  long n)이기 때문에 더더욱 시간 복잡도는 충분하다고 생각했다.

또한 N의 수가 1000개 이하의 자연수라는 점에서 메모리 제한도 충분하다고 생각했다.

 

이번에는 로직은 따로 없다.

 

[최종코드]

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));
        int n = Integer.parseInt(br.readLine());
        int count = 0;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        boolean[] arr = new boolean[1001];

        for (int i = 0; i < arr.length; i++)
            arr[i] = true;

        arr[0] = arr[1] = false;

        for (int i = 2; i < Math.sqrt(arr.length); i++) {

            if (arr[i]) {
                for (int j = i*i; j < arr.length; j += i)
                    arr[j] = false;
            }
        }

        while (st.hasMoreTokens()) {

            if (arr[Integer.parseInt(st.nextToken())])
                count++;
        }

        System.out.println(count);
    }
}

사실 boolean 값 반대로해서 한번 틀렸었다

 

배운점

오랜만에 알고리즘을 공부하게 된 좋은 문제였다!

또한 hasMoreTokens가 계속 헷갈렸는데 이제는 확실하게 배우게 되었다!