[백준] 2581번 : 소수- Java(자바)

이번 문제는 일정 범위에서 소수의 합과 소수들의 최솟값을 찾는 문제였습니다.

Step 0.해답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Search_Sosu2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine()); //M이상
		int N = Integer.parseInt(br.readLine()); //N이하
		int sum = 0;
		int min = N;
		 x : for (int i = M; i <= N; i++) { //N회만큼 반복
			if (i == 1) { //1은 소수가 아님
				continue;
			}
			for (int j = 2; j < i; j++) { //2~i-1까지의 수랑 i랑 나눠서 나머지가 0이면 소수가 아니므로 for문 스킵.
				if (i % j == 0) {
					continue x;
				} 
			}
			sum += i;
			if (min > i) {
				min = i;
			}
		}
		if (sum == 0 ) {
			System.out.println(-1);
			return;
		}
		System.out.println(sum + "\n" + min);
		
	}

}

바로 이전 문제(1978번 소수 찾기)에서 약간만 변형하여 풀었습니다.

Step 1. 문제 접근

1978번의 코드에서 약간 변형을 하여 범위를 입력 받을 수 있게 했고, 이번에는 소수의 개수가 아닌 소수들의 합과 최솟값을 구하는 문제였습니다. 이전과 비슷하게 우선 1은 소수가 아니니 제외하고 나눠서 나머지가 0이면 소수가 아니라는 사실을 갖고 풀었습니다.

Step 2.문제 해결

1. 범위를 입력받았습니다.

int M = Integer.parseInt(br.readLine()); //M이상
int N = Integer.parseInt(br.readLine()); //N이하
int sum = 0;
int min = N;
	x : for (int i = M; i <= N; i++) { //N회만큼 반복
	if (i == 1) { //1은 소수가 아님
		continue;
	}

첫 for문에서는 M이상 N이하이기에 for문의 조건식을 저렇게 주었고 1은 소수가 아니므로 제외하였습니다.

2. 2~ i-1까지의 수를 i와 나눠서 나머지가 0이 나오면 소수가 아니므로 반복문에 continue를 줬습니다.

for (int j = 2; j < i; j++) { //2~i-1까지의 수랑 i랑 나눠서 나머지가 0이면 소수가 아니므로 for문 스킵.
	if (i % j == 0) {
		continue x;
	} 
}

3. 소수의 합과 최소값을 구해줬습니다.

sum += i;
	if (min > i) {
		min = i;
	}
}
if (sum == 0 ) {
	System.out.println(-1);
	return;
}
System.out.println(sum + "\n" + min);

반복문을 정상적으로 빠져나오면 소수이므로 해당 수를 sum에 더해 총 합을 구하는데 사용하였습니다. 그리고 최소값을 구하기 위해서 min 변수를 이용했는데 min의 초기값은 최대 범위인 N으로 줬습니다. 즉 min은 최대값이 처음에 입력되었기 때문에 min이 i보다 크다면 i가 더 작은 수이므로 자연스럽게 최소값을 구하도록 하였습니다. sum이 0일 때는 -1을 출력하도록 하였습니다.

Step 3. 느낀 점

1번 문제와 연결되는 문제였어서 기본 코드에서 약간만 바꿔서 금방 풀 수 있었던 문제 같습니다. 지금까지는 각각의 문제가 큰 범위에서 묶는 느낌이었는데 소수 문제는 차츰차츰 계단식으로 문제를 풀어가는 느낌을 받았습니다.

출처 : 백준 2581번 https://www.acmicpc.net/problem/2581