🔑알고리즘/baekjoon

백준 2581 : 소수 - JAVA(자바) 해결 코드

pkyung 2022. 1. 23. 21:11
반응형

 

백준 2581번 문제는 소수문제입니다.

https://www.acmicpc.net/problem/2581

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

자연수 M부터 N까지의 수 중 소수를 골라 소수의 합과 소수 중 최소값을 출력하는 문제입니다.

 

답지입니다.

해설을 해보자면 prime(int n)이라는 소수를 확인하는 boolean 메서드를 만들고 시작했습니다.

2부터 n/2보다 작은 수까지 나눴을 때 나머지가 0인 수가 없을 때 그 수는 소수가 됩니다.

그리고 최소값을 추가해주기 위해서 자주 사용하는 i++가 아닌 반대로 i--를 사용했습니다. 

버퍼드리더로 메모리의 사용량을 줄였고 다들 비교적 간단하게 해결하실 수 있습니다.

import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int a = Integer.parseInt(br.readLine());
		int b = Integer.parseInt(br.readLine());
		int cnt = 0;
		int s = a;
		for (int i = b; i >= a; i--) {
			if (i == 1) {
				continue;
			}
			if (prime(i)) {
				cnt += i;
				s = i;
			} else {
			}
		}
		if (cnt == 0) {
			bw.write(-1 + "");
		} else {
			bw.write(cnt + "\n" + s);
		}
		bw.flush();
		bw.close();

	}

	static boolean prime(int n) {
		for (int i = 2; i <= n / 2; i++) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

 

 

반응형