[백준 1978] 소수 찾기 (Java)

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

1978번: 소수 찾기

 

접근 방법

소수 찾는 로직은 학교 수업 시간에 자주 다루는 내용이기 때문에 크게 어렵지 않았지만

에라토스테네스의 체라는 알고리즘을 이용하여 구현하였다.

 

에라토스테네스의 체는 가장 작은 수부터 차례로 탐색하여 소수를 찾되, 찾은 소수에 대한 배수를 미리 제거하는 방법이다.

자세한 내용은 이곳을 참고하였다.

 

 

최종 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] numbers = new int[N];
        int count = 0;

        for (int i = 0; i < N; i++) {
            numbers[i] = scanner.nextInt();
        }

        boolean[] isNotPrime = new boolean[10001];

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for (int i = 2; i < isNotPrime.length; i++) {
            int number = i * 2;

            while (number <= 10000) {
                isNotPrime[number] = true;
                number += i;
            }
        }

        for (int i = 0; i < N; i++) {
            int number = numbers[i];

            if (!isNotPrime[number]) {
                count++;
            }
        }

        System.out.println(count);
    }
}