백준 2581 소수 문제풀이 (JAVA)

문제 링크

문제

---

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

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

입력

---

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

---

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

풀이

---

에라토스테네스의 체 알고리즘을 이용했다
에라토스테네스의 체: 위키백과

int sosu[] = new int [5000];
int pivot = -1;
int startPoint = 0;
int answer = 0;
for(int i=2;i<finish+1;i++) {
    if(num[i] != 0) {
		pivot++;
		sosu[pivot] = i;
        if(i >= start) {
                answer += i;
        }
        for(int j=1; i*j<finish+1;j++) {
                num[i*j] = 0;
        }
    }
}

소수를 sosu 배열에 넣으면서, start보다 크면 answer에 더했다.
sosu배열에서 순차적으로 비교하여 start값보다 크거나 같은 값이 처음으로 만족하는 값이 최소값이다. 만약 만족하는 값이 없으면, 입력된 범위에는 소수가 없으므로 -1을 출력한다.

소스코드

---

import java.util.*;
import java.io.*;
public class Main{
    
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
       
        final int start = Integer.parseInt(br.readLine());
        final int finish = Integer.parseInt(br.readLine());
        int num[] = new int [finish+1];
        for(int i=0;i<finish+1;i++) {
            num[i] = i;
        }
        num[1] = 0;
        int sosu[] = new int [5000];
        int pivot = -1;
        int startPoint = 0;
        int answer = 0;
        for(int i=2;i<finish+1;i++) {
            if(num[i] != 0) {
                pivot++;
                sosu[pivot] = i;
                if(i >= start) {
                    answer += i;
                }
                for(int j=1; i*j<finish+1;j++) {
                    num[i*j] = 0;
                }
            }
        }
        
        for(int i=0;i<pivot+1;i++) {
            if(sosu[i]>start-1) {
                startPoint = sosu[i];
                break;
            }
        }
        
        if(startPoint==0) {
            sb.append(-1);
             sb.append("\n");  
        }else {
            sb.append(answer);
            sb.append("\n");
            sb.append(startPoint);
            sb.append("\n");  
            
        }
             
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }

    
}