[Java] 백준(실버-5) 2581번 - 소수

입출력 예시

Input-1
60
100
Output-1
620
61

Input-2
64
65
Output-2
-1

문제 풀이

---

이 문제는 간단하게 M부터 N까지의 수중에서 소수를 찾아, 소수 중 최소값과 소수들의 합을 구하면 된다.
ArrayList를 활용하여 소수들을 찾아 담아 최소값과 소수의 합을 구할 수 있다.

코드를 작성해보자.

int M = Integer.parseInt(br.readLine());
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> prime_list = new ArrayList<>();
int sum = 0;

먼저, M과 N을 입력받고, 소수들을 저장할 ArrayList와 소수들의 합을 저장할 sum 변수를 초기화한다.

for(int i=M; i<=N; i++) if(isPrime(i) == 2) prime_list.add(i);
for(int num : prime_list) sum += num;

if(prime_list.size()>0) bw.write(sum + "\n" + prime_list.get(0) + "\n");
else bw.write("-1"+"\n");

M부터 N까지 반복하면서 소수들을 찾아 ArrayList에 저장한다.
primeList를 전부 탐색하여 sum에 더하면 소수들의 합을 구할 수 있다. M은 N보다 작거나 같기에 prime_list는 오름차순으로 저장되어 있다. 그러므로 첫번째 원소가 최소값임을 알 수 있다.

작성코드

import java.io.*;
import java.util.*;

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 M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> prime_list = new ArrayList<>();
        int sum = 0;

        for(int i=M; i<=N; i++) if(isPrime(i) == 2) prime_list.add(i);
        for(int num : prime_list) sum += num;

        if(prime_list.size()>0) bw.write(sum + "\n" + prime_list.get(0) + "\n");
        else bw.write("-1"+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
    public static int isPrime(int num) {
        int count = 0;
        for(int i = 1; i <= num; i++) {
            if(num % i == 0) count += 1;
            if(count >= 3) return count;
        }   
        return count;
    }
}

회고

• M부터 N까지 소수가 얼마나 존재하는지 모르기에 ArrayList를 활용하여 소수들을 담아서 최솟값과 소수들의 합을 구할 수 있었다.