[백준] 2581번(Java)

📖 소수

[ 문제 ]
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

💡풀이

• 기존의 풀이 방식은 주어진 범위 내에 있는 숫자 n에 대해 2부터 n-1까지 나눠봐서 나머지가 0인지 아닌지 확인함으로써 각 숫자들이 소수인지를 확인하는 Brute Force 방식을 이용함.
• 소수 계산 방식에는 "에라토스테네스의 체" 라는 방식이 더 효율적이라는 것을 알게 되었다.
  
  

에라토스테네스의 체

• 효율적인 소수 찾기 알고리즘
• 2부터 시작해서 소수인지 확인하고자 하는 숫자 범위의 최댓값인 N의 제곱근인 $\sqrt{N}$ 전까지 모든 수의 배수들을 전부 제외하면서 찾아가는 방식이다.
• ex) 소수인지 확인하고자 하는 숫자 범위 : 2 ~ 120
  1. size가 120인 boolean[ ] 형태의 배열을 생성한다.
  2. 2의 배수를 전부 true로 바꾼다.(2는 소수이기 때문이 false로 남겨둔다.)
  3. 3부터 $\sqrt{120}$보다 작은 수까지(10까지) 수들 중, false로 남아 있는 수들의 배수들을 전부 지운다.
  4. 배열 중 false로 남아 있는 값들이 전부 소수, true로 변한 값들은 소수가 아니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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());
        boolean[] ans = new boolean[N + 1];
        ans[0] = true;
        ans[1] = true;

        for(int i = 2; i <= Math.sqrt(N + 1); i ++ ){
            // 체크된걸 확인 -> 이미 더 작은 약수의 배수로 확인을 마친 배열들임.
            if(ans[i]) continue;
            for(int j = i * i ; j < N + 1; j += i ){
                ans[j] = true;
            }
        }
        int a = 0;
        int min = 0;
        for(int k = M ; k < N + 1 ; k++){
            if(!ans[k]){
                a += k;
                if(min == 0){ min = k; }
            }
        }
        if(a == 0){
            System.out.println(-1);
        } else{
            System.out.println(a);
            System.out.println(min);
        }
    }
}

백준 2581번 : https://www.acmicpc.net/submit/2581/88003640