[백준] 소수(소수들의 합과 최솟값)

---

백준 온라인 저지 2581번 - 소수

지난 소수 구하기 알고리즘 포스팅에서 공부한 것을 적용하기 위해 소수 구하기 알고리즘(에라토스테네스의 체)를 활용한 문제를 풀이했다.

지난번 풀이한 소수 구하기 문제와 다르게 범위 내의 소수를 구한 후 해당 소수들의 합과 최솟값을 구하는 문제였다. 알고리즘이 되게 간단해서 두 번 정도 풀이하니 완전하게 몸에 익은 것 같다.

PrimeNumberSumMin.java

package com.example.Baekjoon;

/**
 * 백준 2581 소수
 * 에라토스테네스의 체 알고리즘으로 풀이
 * int M
 * int N
 * M이상 N이하의 소수를 구하여 소수들의 합과 최솟값을 리턴
 */
public class PrimeNumberSumMin {
    public int[] getPrimeNumberSumMin(int M, int N) {
        int[] arr = new int[N + 1];

        int sum = 0;
        int min = Integer.MAX_VALUE;

        // 배열 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        // 2부터 시작
        for (int i = 2; i < Math.sqrt(arr.length); i++) {
            if (arr[i] == 0) {
                continue;
            }
            for (int j = i + i; j < arr.length; j = j + i) {
                arr[j] = 0;
            }
        }

        for (int i = M; i < arr.length; i++) {
            if (arr[i] != 0) {
                sum += arr[i];
            }
            if (arr[i] != 0 && arr[i] < min) {
                min = arr[i];
            }
        }

        // 소수가 있으면 합과 최솟값 리턴, 없으면 -1 리턴
        return sum != 0 ? new int[] { sum, min } : new int[] { -1 };
    }
}

PrimeNumberSumMinTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class PrimeNumberSumMinTest {
    @Test
    public void testPrimeNumberSumMin() {
        PrimeNumberSumMin psm = new PrimeNumberSumMin();

        int[] result1 = psm.getPrimeNumberSumMin(60, 100);
        int[] result2 = psm.getPrimeNumberSumMin(64, 65);

        int[] expected1 = new int[] { 620, 61 };
        int[] expected2 = new int[] { -1 };

        assertArrayEquals(expected1, result1);
        assertArrayEquals(expected2, result2);
    }
}