Baekjoon2581: 소수

문제

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

 

추상화

바로 이전 문제인 소수찾기와 비슷하다
1) 배열의 크기를 10001로 만들어주고 소수를 표시한다
2) 탐색을 M부터 N까지 해서 소수로 표시되어있으면 그 값을 sum에 더한다
3) 처음 만나는 소수를 따로 저장한다. 논리변수를 이용한다

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 boolean[] prime = new boolean[10001];
	 int devide =0;
	 int sum=0;
	 boolean first = true;
	 int min = 0;
//소수 배열 만들기, 반복문에서 사용되는 변수 미리 만들기
	 for(int i=2; i<10001; i++) {
		 devide = 10000/i;
		 for(int j=2; j<=devide; j++) {
			 prime[i*j] = true;
//false로 남은 애들만 소수다
		 }
	 }
	 prime[0] = true;
	 prime[1] = true;
//0과 1은 특별히 구분
	 int M = Integer.parseInt(br.readLine());
	 int N = Integer.parseInt(br.readLine());

	 for(int i=M; i<=N; i++) {
		 if(prime[i]==false) {
			 sum += i;

			 if(first) {
				 min = i;
				 first = false;
			 }
//처음 소수값을 가져오면서 논리변수를 false로 만든다
		 }
	 }
	 if(sum >0) {
	 System.out.println(sum);
	 System.out.println(min);
	 } else if(sum==0){ System.out.println(-1);}
}
}