[백준] 소수 구하기

---

백준 온라인 저지 1929번 - 소수 구하기

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

단순하게 딱 소수를 구하는 문제라서 바로 알고리즘을 적용하면 풀이가 되는 문제였다.
알고리즘도 복잡하지 않고 문제 유형에서 그래도 자주 출제되는 문제라고 하니 꼭 기억해두어야겠다.

PrimeNumber.java

package com.example.Baekjoon;

import java.util.ArrayList;
import java.util.List;

/**
 * 백준 1929 소수 구하기
 * 에라토스테네스의 체 알고리즘으로 풀이
 * int M
 * int N
 * M이상 N이하의 소수를 구하기
 */
public class PrimeNumber {
    public int[] getPrimeNumber(int M, int N) {

        List<Integer> answer = new ArrayList<>();
        int[] pNumbers = new int[N + 1];

        // 배열 초기화
        for (int i = 0; i <= N; i++) {
            pNumbers[i] = i;
        }
        // 최대값(N)의 제곱근만큼 반복
        for (int i = 2; i <= Math.sqrt(N); i++) {
            if (pNumbers[i] == 0) {
                continue;
            }

            // 선택된 수의 배수를 삭제(0으로 업데이트)
            for (int j = i + i; j <= N; j = j + i) {
                pNumbers[j] = 0;
            }
        }

        for (int p = M; p < pNumbers.length; p++) {
            if (pNumbers[p] != 0) {
                answer.add(p);
            }
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

PrimeNumberTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class PrimeNumberTest {
    @Test
    public void testPrimeNumber() {
        PrimeNumber p = new PrimeNumber();

        int[] result = p.getPrimeNumber(3, 16);

        assertArrayEquals(new int[] { 3, 5, 7, 11, 13 }, result);
    }
}