백준 알고리즘 | 1978번 문제: 소수 찾기

출처

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

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4 1 3 5 7

예제 출력 1

알고리즘 분류

수학
정수론
소수 판정
에라토스테네스의 체

문제 풀이

통과한 코드 (1)

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 {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            int count = 0;
            for (int i = 0; i < n; i++) {
                int a = Integer.parseInt(st.nextToken());
                if (isPrime(a)) {
                    count++;
                }
            }

            System.out.println(count);
        }
    }

    private static boolean isPrime(int num) {
        if (num == 1) // 1은 소수x
            return false;

        //for (int i = 2; i < num; i++) { // 모든 경우를 다 확인
        //for (int i = 2; i <= num/2; i++) { // 해당 숫자의 절반까지만 확인
        for (int i = 2; i * i <= num; i++) { // 제곱근을 이용한 방법
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

통과한 코드: 에라토스테네스의 체를 이용한 방식
에라토스테네스의 체라는 소수를 찾는 방법으로 풀어보자.

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 {

        // 에라토스테네스의 체를 만든다.
        boolean[] prime = new boolean[1001]; // 소수판별 배열 선언
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i <= Math.sqrt(1000); i++) {
            if (prime[i] == true)
                continue;
            for (int j = i * i; j < 1001; j = j + i)
                prime[j] = true;
        }

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            // 입력
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());

            // 반복하면서 에라토스테네스의 체에 포함되었는지 찾는다.
            int count = 0;
            for (int i = 0; i < n; i++) {
                int a = Integer.parseInt(st.nextToken());
                if (prime[a] == false) {
                    count++;
                }
            }

            // 출력
            System.out.println(count);
        }
    }
}

참고

위키백과 | 에라토스테네스의 체

최종 수정 : 2022-04-20