[백준 자바] 2581번(소수) - 에라토스테네스의 체

난이도 - 브론즈 2

문제

자연수 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을 출력한다.

 

---

 

728x90

에라토스테네스의 체를 사용한다. 2부터 n까지의 모든 수를 나열하고 2의 배수들을 모두 지운다. 남아있는 수 중에서 다음 수를 소수로 선택하고 그 수의 배수들을 모두 지운다. 이 과정을 범위의 끈까지 반복하고 남아있는 수들이 소수이다.

import java.io.*;
import java.util.Arrays;

public class Main2581 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		boolean[] isPrime = sieveOfEratosthenes(N);

		int firstPrime = -1;
		int sum = 0;

		for (int i = M; i <= N; i++) {
			if (isPrime[i]) {
				if (firstPrime == -1) {
					firstPrime = i;
				}
				sum += i;
			}
		}

		if (firstPrime == -1)
			bw.write("-1");
		else
			bw.write(sum + "\n" + firstPrime);

		bw.flush();
		br.close();
		bw.close();
	}

	static boolean[] sieveOfEratosthenes(int max) {
		boolean[] isPrime = new boolean[max + 1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;

		for (int i = 2; i * i <= max; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j <= max; j += i) {
					isPrime[j] = false;
				}
			}
		}

		return isPrime;
	}
}