[수학] 백준 2581 소수

2581번: 소수

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

 

# 코드

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

public class Main {
    public static boolean prime[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        // 소수를 표시할 배열 생성
        prime = new boolean[N + 1];
        get_prime();

        // 소수의 합 sum, 최솟값 min
        // min : 일단 최대 정수로 초기화해놓고 첫 소수가 나오면 해당 값을 저장함
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = M; i <= N; i++) {
            // false == 소수
            // prime[i]가 소수인 경우
            if (prime[i] == false) {
                sum += i;

                // 첫 소수가 최솟값임
                if (min == Integer.MAX_VALUE) {
                    // 최솟값 저장
                    min = i;
                }
            }
        }

        // 출력
        // 소수가 없는 경우 (=sum이 0일 경우) -1
        if (sum == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
        
        br.close();
    }

    // 에라토스테네스 체 알고리즘
    public static void get_prime() {
        // 0과 1은 소수가 아님
        prime[0] = true;
        prime[1] = true;

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            // 이미 체크된 배열일 경우 skip
            if (prime[i]) {
                continue;
            }

            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

• Integer.MAX_VALUE : 최대 양의 정수
• Math.sqrt() : 제곱근 함수 (ex: Math.sqrt(16) 의 리턴 값은 4이다.)

 

에라토스테네스의 체는 소수를 구하는 대표적인 방법 중 하나이다.

 

에라토스테네스의 체

" k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다 "

 

 

소수와 알고리즘 이해는 아래 블로그를 참고했다.

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

그리고 코드도 참고했다. 공부에 많이 도움이 되었다.

[백준] 2581번 : 소수 - JAVA [자바]