백준알고리즘 1929번 소수 구하기

1929번 소수 구하기 문제는 소수를 찾는 알고리즘 문제이다.

 

소수는 약수로 1과 자기 자신만을 가지는 정수이다. 예를 들어, 2의 약수는 1, 2이며, 4의 약수는 2, 2이다. 4의 약수로 1, 4가 아니기 때문에 4는 소수가 아니다. 반대로 2는 1과 자기 자신인 2를 가지고 있기 때문에 소수이다.

 

소수를 구하는 알고리즘으로는 제곱근을 이용한다. N이 주어졌을 때, 2부터 N의 제곱근 범위의 숫자 중 나누어지는 경우가 있다면 해당 N은 소수가 아닌것으로 판단할 수 있다.

for(int i = 2; i <= sqrt(N); i++) {
    if(N % i == 0) {
         // N은 소수가 아님
         return false;
     }
}

주의 사항으로는 문제 예제 출력과 동일한 값을 구하더라도 N이 1인 경우를 따로 처리하지 않으면 문제 제출 시 에러가 발생한다.

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

/**
 * 소수 구하기 문제<br>
 * 알고리즘 분류 : 에라토스테네스의 체
 * 
 * @author jayden-lee
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int startNumber = scanner.nextInt();
        int endNumber = scanner.nextInt();

        List<Integer> primeNumbers = findPrimeNumberRange(startNumber, endNumber);

        // 소수 숫자 결과값 출력
        for (int primeNumber : primeNumbers) {
            System.out.println(primeNumber);
        }

        scanner.close();
    }

    /**
     * 두 개의 숫자를 인자로 전달 받아서 범위 내에 있는 모든 소수를 찾아서 반환한다.
     * 
     * @param startNumber int
     * @param endNumber int
     * @return List<Integer>
     */
    private static List<Integer> findPrimeNumberRange(int startNumber, int endNumber) {
        List<Integer> primeNumbers = new ArrayList<>();

        for (int i = startNumber; i <= endNumber; i++) {
            // 소수인지 체크한다. 소수이면 List에 요소를 추가한다.
            if (isPrime(i)) {
                primeNumbers.add(i);
            }
        }

        return primeNumbers;
    }

    /**
     * 인자로 전달 받는 숫자가 소수인지 판별하고 boolean 값을 반환한다.
     * 
     * @param number int
     * @return boolean
     */
    private static boolean isPrime(int number) {
        // 숫자가 2보다 작으면 false 반환한다.
        if(number < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if(number % i == 0) {
                return false;
            }
        }

        return true;
    }

}