문제

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

풀이

해당 문제는 에라토스테네스 체 알고리즘을 사용하면 쉽게 풀 수 있다. 범위가 m부터 n까지이기 때문에 배열의 크기를 n+1로 하여 만들었다.

그 후 true로 채운 뒤 1은 소수가 아니기 때문에 1부분을 false로 바꾼다.

그다음 2부터 n의 제곱근까지 for문을 돌리면서 제일 작은것부터 자기자신을 뺀 i의배수들을 false로 바꾸어 준다. (에라토스네테스 체)

이제 배열에는 소수만 남아 있다. 그러면 m부터 n까지 true인 것만 뽑아서 최솟값을 찾고 누적 합을 찾으면 되는 것이다.

소스

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int m = sc.nextInt();
		int n = sc.nextInt();

		boolean[] arr = new boolean[n + 1];

		Arrays.fill(arr, true);
		arr[1] = false;

		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (arr[i] == true) {
				int j = 2;
				while (i * j <= n) {
					arr[i * j] = false;
					j += 1;
				}
			}
		}

		int min = n + 1;
		int sum = 0;
		for (int i = m; i <= n; i++) {
			if (arr[i]) {
				min = Math.min(min, i);
				sum += i;
			}
		}

		if (sum != 0) {
			System.out.println(sum);
			System.out.println(min);
		} else {
			System.out.println(-1);
		}

	}

}