[백준 / Java] 1978번 : 소수 찾기

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

1978번: 소수 찾기

 

---

◎ 문제

 

---

◎ 코드

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        // n 입력받기
        int n = sc.nextInt();
 
        // n개 만큼의 리스트 만들기
        int[] numList = new int[n];
 
        // n개의 수 입력받아 리스트에 넣기
        for (int i = 0; i < n; i++) {
            numList[i] = sc.nextInt();
        }
 
        // 소수 리스트 만들기
        // 1~1000까지의 리스트 생성
        int [] primeList = new int[1001];
        for (int i = 0; i <= 1000; i++) {
            primeList[i] = i;
        }
        primeList[1] = 0;
 
        // 에라토스테네스의 체 사용
        for (int i = 2; i <= 1000 ; i++) {
            int k = 2;
            if (primeList[i] != 0) {
                try {
                    while(true) {
                        primeList[i*k] = 0;
                        k += 1;
                    }
                } catch (Exception e) {
                    continue;
                }
            }
        }
 
        // 소수라면 cnt 하나씩 더하기
        int cnt = 0;
        for (int num:numList) {
            if (primeList[num] == num) {
                cnt+=1;
            }
        }
 
        System.out.println(cnt);
    }
}

 

---

◎ 풀이 및 기록

 

먼저 문제의 입력조건에서 1000이하의 자연수라 했으므로 1부터 1000까지 리스트를 생성한다. 그 후 에라토스테네스의 체를 이용하여 소수를 판정하여 소수가 아닌 수는 0으로 넣고 소수인 수는 그대로 둔다. 이때 소수를 넣은 리스트의 소수값과 인덱스값이 같기 때문에 입력받은 값을 순회하며 소수 리스트에서 입력받은 값에 위치해있는 값이 0이 아니라면 소수라고 판정하여 cnt를 하나씩 더해주고 마지막으로 출력해준다.

 

* 에라토스테네스의 체란 고대 그리스 수학자 에라토스테네스가 발견한 소수 판정법으로 2부터 소수를 구하고자 하는 구간의 모든 수를 나열하여 순서대로 자기자신만 제외하고 배수들은 모두 지우는 방식이다. 이 방벙은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 부른다.