백준 2581번

소수

문제

자연수 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과 그수 자신 이외의 자연수로는 나눌 수 없는, 1보다 큰 자연수이다.
바깥 for문 내부에 flag를 두어서, 소수가 아니라고 판명되면 flag를 증가시킨다.
i%j가 0이면 소수이다.
flag가 0일때가 소수이므로 이 때의 i값을 sum에 모두 더한다.
또한 min은 처음에 N (최댓값)으로 두고, 소수일 때 i값이 min보다 작으면 min 값이 곧 i 값이다.

코드

import java.io.*;

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());
	        br.close();
	        
	        int sum = 0;
	        int min = N;
	        
	        for(int i = M; i <= N; i++) {
	        	int flag = 0;
	        	
	        	if(i == 1)
	        		flag++;
	        	
	        	for(int j=2; j < i; j++) {
	        		if(i % j == 0) {
	        			flag++;
	        			break;
	        		}
	        	}
	        	
	        	if(flag == 0) {
	        		sum += i;
	        		
	        		if(min > i)
	        			min = i;
	        	}
	        }
	        
	        if(sum == 0)
	        	System.out.println(-1);
	        else {
	        	System.out.println(sum);
		        System.out.println(min);
	        }
	}
}