[백준] 1978번 : 소수 찾기 – JAVA [자바]

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

1978번: 소수 찾기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1978번 소수 찾기는 실버 5 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 N개의 자연수가 주어지고 이 N개 자연수들 중에서 소수가 몇 개인지를 출력하면 된다.

 

이 문제는 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다. 에라토스테네스의 체를 잘 모르면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/182

[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes)

 

우선 에라토스테네스의 체 메서드 primeNumber에서 크기가 1000인 배열 arr을 선언한다. 이 이유는 주어지는 수는 모두 1000 이하라고 문제에 명시되어 있기 때문이다. 그리고 그 arr의 각 인덱스를 초기화해준다.

 

초기화를 다 하면 2부터 시작해서 모든 배수들을 arr에서 지워준다. 그러면 그 배열에는 값이 0인 인덱스와 값이 0이 아닌 인덱스로 나뉘게 된다. 즉, 배열에 남아있는 수들은 모두 소수라는 것이다.

 

이제 main 함수에서 입력받은 수를 i라고 하겠다. 만약에 arr [i]가 0이 아니라면 소수인 뜻이므로 count를 1씩 증가시켜주고 마지막에 count 값만 출력해주면 된다.

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int count;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        count = 0;
        int n = Integer.parseInt(br.readLine());
        primeNumber();  //에라토스테네스의 체 메서드 호출
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            //num이 지워진 수가 아니면 소수이므로 count + 1
            if (arr[num] != 0) count++;  
        }
        System.out.print(count);
    }

    //에라토스테네스의 체 메서드
    static void primeNumber() {
        arr = new int[1001];  //n의 범위가 1000까지이므로 1000 크기의 배열 선언
        int n = 1000;
        //배열 초기화
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }

        //2부터 시작해서 i의 배수들을 배열에서 지워준다
        for (int i = 2; i <= n; i++) {
            //이미 지워진 수는 건너뛴다
            if (arr[i] == 0) continue;
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }
    }
}