[알고리즘/백준] 1978 소수 찾기(자바, 에라토스테네스의 체)

문제

https://www.acmicpc.net/problem/1978

풀이 코드

• 에라토스테네스의 체 알고리즘을 사용하여 풀이

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

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[] arr = new int[n];

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

        //배열의 인덱스는 수, 값이 true 이면 소수가 아니다.
        boolean[] isNotPrimes = new boolean[max+1];

        //1은 소수가 아니다.
        isNotPrimes[1] = true;

        //에라테네스 체 알고리즘 사용하여 1 ~ max 범위의 소수 판별
        for (int i = 2; i <= max; i++) {
            if (!isNotPrimes[i]) {
                for (int j = i * 2; j <= max; j += i) {
                    isNotPrimes[j] = true;
                }
            }
        }

        int count = 0; //소수 개수

        for (int num : arr) {
            if (!isNotPrimes[num]) {
                count++;
            }
        }

        System.out.println(count);
    }
}

 

에라토스테네스의 체 알고리즘은 소수를 판별할 때 자주 사용되는 알고리즘이다.
해당 알고리즘에 대해 알고싶다면 아래 링크의 게시물이 도움이 될 것이다.
https://developer-hm.tistory.com/64