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

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

2581번: 소수

 

---

• 문제

 

 

---

• 문제 풀이

백준 2581번 소수는 실버 5 난이도의 수학 문제이다. 이 문제에서는 입력으로 자연수 M과 N이 주어진다. 그리고 M이상 N이하인 소수들의 합과 소수의 최솟값을 출력하면 된다. 만약에 이 범위 안에 소수가 없을 때는 -1을 출력하면 된다.

 

이 문제는 소수 판별 알고리즘인 에라토스테네스의 체를 이용해서 풀 수 있다. 에라토스테네스의 체 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. 

 

 https://propercoding.tistory.com/182

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

 

이 문제에서 M과 N의 범위가 10,000 이하라는 것이 주어졌다. 그리고 M이 1, N이 10,000일 수도 있으니 크기가 10,000인 배열을 선언하고 초기화해준다. 

 

그리고 2부터 시작해서 N까지 모든 배수들을 배열에서 지워준다. 이 이유는 배수라는 뜻은 약수가 있기 때문에 소수가 되지 못해서 이다. 따라서, 2부터 N까지의 모든 배수들을 배열에서 지워주면 배열에는 소수들밖에 남지 않는다. 하지만, M과 N 사이에 소수가 없을 때는 모든 수가 지워진 경우이다. 

 

이제 for-loop을 M부터 N까지 돌려서 소수들의 합과 소수의 최솟값을 구해주면 된다.

 

자세한 코드는 밑에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {

    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());
        primeNumber(m,n);
    }

    //에레토스테네스의 체 메서드
    static void primeNumber(int m, int n) {
        int[] arr = new int[10001];
        int min = Integer.MAX_VALUE;
        int sum = 0;

        //배열 초기화
        for (int i = 2; i <= 10000; i++) {
            arr[i] = i;
        }

        //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;
            }
        }

        //소수들의 합 구하기
        for (int i = m; i <= n; i++) {
            if (arr[i] != 0) {
                min = Math.min(min, i);
                sum += i;
            }
        }
        if (min > n) {
            System.out.print(-1);
        } else {
            System.out.print(sum + "\n" + min);
        }
    }
}