[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. 첫번째 입력값은 M이 된다.
2. 두번째 입력값은 N이 된다.
3. 길이가 N인 배열을 만든다. (소수를 저장하기 위한 배열)
4. 길이가 M-N+1인 배열을 만든다. (M과 N 사이의 자연수를 저장하기 위한 배열)
5. M과 N 사이의 자연수를 구해서 5번 배열에 넣는다.
6. 5번 배열 안의 자연수 중 소수를 구해서 4번 배열에 넣는다.
7. 4번 배열의 첫 번째 값이 최솟값이 된다.
8. 반복문을 사용해서 4번 배열의 총 합을 구한다.
9. 값을 출력한다.

package lv_1;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class B2581 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int m = Integer.parseInt(br.readLine());
		int n = Integer.parseInt(br.readLine());

		//m과 n 사이의 소수를 저장하기 위한 배열
		int[] arr = new int[n];
		int idx = 0; //배열의 인덱스를 의미하는 변수(소수를 저장할 때 필요)

		//m과 n 사이의 자연수를 저장하기 위한 배열
		int[] num = new int[n-m+1];

		//배열에 m과 n 사이의 자연수를 저장한다.
		for(int i=0;i<num.length;i++) {
			num[i] = m+i;
		}

		//배열의 길이만큼 반복한다.(배열 내의 전체 데이터를 검사하기 위해)
		for(int i=0;i<num.length;i++) {

			int count = 0; //소수 체크를 위해 필요한 변수

			//2부터 n-1번째 값으로 반복해서 나눈다.
			for(int j=2;j<num[i];j++) {
				if(num[i]%j==0) { //나머지가 0이면 소수 아님
					count++;
					break; //반복문 빠져나가고 다음 수 체크
				}
			}

			//count가 0이라는 것은 나머지가 0인 경우가 한번도 없다는 의미
			//값이 1일 때는 for문에 들어가지 못하므로 무조건 count=0이기 때문에,
			//1이 소수로 인식되는 것을 막기 위해 조건 추가
			if(count==0 && num[i]!=1) {
				arr[idx] = num[i]; //소수면 배열에 넣는다.
				idx++; //인덱스값 ++
			}
		}

		//만약 소수를 저장한 배열의 첫 번째 값이 0이면
		//(저장된 데이터가 없다는 것을 의미한다.)
		if(arr[0]==0) {
			System.out.println(-1);
		}else {
			int min = arr[0]; //최솟값은 배열의 첫 번째 값
			int total = 0; //총합을 구하기 위한 변수

			//반복문을 통해 총합 구하기
			for(int i=0;i<arr.length;i++) {
				total += arr[i];
			}

			System.out.println(total);
			System.out.println(min);

		}
	}
}