백준 2581번 - 소수(Java)

백준 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을 출력한다.

풀이 과정

1. 소수 판별을 해서 최솟값과 소수들의 총합을 구해야 한다. 최솟값을 구하는 알고리즘을 사용 해도 되지만 그냥 큰 값부터 for문을 돌리고 i-- 처리를 하면 맨 마지막 소수가 최솟값이 되므로, 쓸 필요가 없어서 사용하지 않았다.

2. boolean 함수로 소수 판별하는 함수를 만들었다.

3. 문제 풀이가 틀렸다고 나왔는데, 반례를 찾아보니 숫자 1을 입력했을때의 예외처리를 하지 않아 틀렸었다.

수정하니 맞았다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int sum=0;
        int min=M;
        
        for(int i=N; i>=M; i--) {
        	if(prime(i)==true) {
        		min=i;
        		sum += i;
        	}
        }
        if(sum==0) {
        	System.out.println(-1);
        }
        else {
        	System.out.println(sum);
        	System.out.println(min);}
    }
    static boolean prime(int i) {
    	if(i<2) {
    		return false;
    	}
    	for(int j=2; j<i; j++) {
    		if(i%j==0) {
    			return false;
    		}
    	}
    	return true;
    }
}