[백준/Java] 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

60
100

 

| 예제 출력 1

620
61

 

| 예제 입력 2

64
65

 

| 예제 출력 2

-1

 

| 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

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());
		
		ArrayList<Integer> arr = new ArrayList<Integer>();
		int sum = 0;
		
		for(int i=M; i<=N; i++)
		{
			int count = 0;
			
			for(int j=2; j<i; j++)
			{
				if(i%j == 0)
					count++;
			}
			
			if(count==0 && i != 1)
				arr.add(i);
		}
		for(int num : arr)
			sum += num;
		
		if(sum != 0)
		{
			System.out.println(sum);
			System.out.println(arr.get(0));
		}
		else
			System.out.println("-1");
		
	}
}

| 정리

이전에 소수 관련 문제 풀었던 거랑 비슷하게 소수가 아니면 count에 1씩 증가 시킨 후에, count 가 0인 애들만 배열에 저장했다.

몇개의 수가 배열에 저장될지 모르니 Array 가 아닌 ArrayList를 사용했고

제일 작은 수 부터 배열에 저장되니 대소 비교를 해줄 필요 없이 0번째 방에 있는 값을 가져오면 그것이 바로 최솟값!