[백준] 1978번 소수찾기 - Java[에라토스테네스의 체]

[백준] 1978번 소수찾기 - Java[에라토스테네스의 체]

 

문제 출처

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

1978번: 소수 찾기

 

---

※ 풀이

범위내에 있는 수들 중에 소수만 고르는 문제이다.

하나의 수만 소수인지 아닌지 판별하는 경우에는 다른 방법을 쓸 수도 있지만 

이렇게 범위내의 모든 소수를 골라야 하는 경우에는 에라토스테네스의 체라는 방법을 사용한다.

 

• [에라토스테네스의 체 풀이]

1. N 까지의 범위를 가지는 배열을 만든다.

(해당 index 의 수가 소수인지 아닌지 판별해주는 역할)

 

2. 제일 작은 소수인 2부터 아래 과정을 돌린다.

2-1) 현재 지워지지 않은 수 x 를 중심으로 x를 제외한 x의 배수들은 모두 소수가 아니므로 배열에서 지운다.

-> x 가 이미 지워져있다면 바로 x+1로 넘어간다.

2-2) 다음 수 x+1 로 넘어가서 2-1을 반복한다.

 

이렇게 배열의 끝까지 반복문을 돌린 뒤 아직 지워지지 않은 수가 소수라고 보면 된다.

 

---

※ 소스코드

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

public class Main {

    static boolean[] isNotPrime = new boolean[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] data = new int[n];

        String[] split = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(split[i]);
        }

        isNotPrime[0] = true;
        isNotPrime[1] = true;
        for (int i = 2; i <= 1000; i++) {
            if (!isNotPrime[i]) {
                erase(i);
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int number = data[i];
            if(!isNotPrime[number]){
                answer++;
            }
        }
        System.out.println(answer);
    }

    //number 를 제외한 수들을 지운다.
    static void erase(int number) {
        int length = 1000 / number;
        for (int i = 2; i <= length; i++) {
            isNotPrime[number * i] = true;
        }
    }
}

---