[백준 2581번] 소수 (JAVA)

BOJ - [2581] 소수

---

🖍 M부터 N까지의 소수를 찾고, 그 소수들의 합과 그 중 최소값인 소수를 출력하는 문제
(link) 2581 소수

---

[풀이 과정]

소수를 판별하는 가장 효율적인 방법을 두고 다른 방법을 써서 풀었기 때문에... 나중에 수정해서 다시 풀어야 할 것 같다.

우선 개념 설명 먼저하겠다.

소수란 1과 자기 자신만을 약수로 가지는 자연수이다.
0과 1은 소수가 아니며, 2를 제외한 짝수들은 모두 약수로 2를 가지기 때문에 소수가 아니다.

소수를 판별하는 방법은 총 세 가지이다. 1부터 N까지 수 중에서 소수를 찾고 있다고 가정하고 이야기하겠다.

---

<1. N 미만 자연수로 모두 나눠보기>

소수는 1과 자기 자신만을 약수로 가진다. 따라서 N보다 작은 자연수로 모두 나누어볼 때 나누어 떨어지는 경우가 있으면 N은 소수가 아니게 된다.

이 방법에서 조금 더 발전시킬 수 있다.

2를 제외한 짝수들은 모두 소수가 아니므로 조건문을 이용하든, 증감을 이용하든지 해서 짝수들은 제외시키는 방법이 있겠다.

시간 복잡도는 당연히 O(n)이 될 것이므로 아주 비효율적이라고 할 수 있겠음.

 

<2. √N 이하 자연수로 모두 나눠보기>

1번의 방법보다 검사해야하는 수의 범위를 조금 줄인 방법이다.
왜 √N 이하의 자연수로 나누면 판별이 될까? 임의의 자연수 N이 있다고 가정하자.

x * y = N 일 때, x와 y의 범위는 1 ≤ x,y ≤ N이다.
이때 x, y 둘 중 하나는 무조건 √N보다 작음이 보장되므로 √N 이하 자연수 중 나누어 떨어지는 수가 있다면 1,N을 제외한 다른 자연수가 약수라는 의미이므로 소수에서 제외되는 것이다.

말로만 보면 솔직히 이해가 잘 안된다. 그렇기 때문에 내가 이해한 대로 시각적 자료와 함께 설명하겠다.

예시를 들어보면 조금 더 쉽게 이해할 수 있다.

 

1. N이 소수(Prime Number)가 아닌 경우
소수가(Prime Number) 아닐 경우 √N은 자연수로 나오거나, 소수(여기서 말하는 소수는 x.xx 따위의 정수가 아닌 유리수를 말한다)로 나온다. 아래의 예시를 보자.

위 그림을 보면 알 수 있듯이 소수가 아닐 경우 x * y를 나열해보면 중간값이 무조건 생기며, 그 아래로 1이 아닌 수 중에서 약수인 수가 보일 것이다.

√N의 경우 x * y가 나열된 값 중에서 중간에 해당하는 수가 되기 때문에 1이 아닌 √N보다 작은 수로 나눠질 경우 다른 약수가 있는 것으로 판별된다. 따라서 

 

2. N이 소수(Prime Number)인 경우
x * y가 어떻게 나올까? 아래의 예시를 보자.

위 그림에서 보이듯, x * y를 나열하면 두 가지 경우밖에 생기지 않는다.

중간에 값이 없고 xy 아니면 yx꼴이기 때문에 √N보다 작은 값 중에서 약수가 생기지 않고 오로지 1과 자기 자신만이 약수가 된다.

따라서 .. √N 이하의 수로 나눠서 나누어 떨어지면 소수가 될 수 없다.

√N만큼 반복문을 돌 것이기 때문에 시간복잡도는 O(√N)이다.

 

<3. 에라토스테네스의 체>

소수를 판별하는 방법 중에 가장 효율적(일 거다 아마도)이고 빠른 유명한 방법이다. 설명도 아주 간단하게 할 수 있다.

k=2부터 √N이하의 정수까지 반복하며, 자연수들 중 k 제외 k의 배수들은 무조건 소수가 아니다.

위에서 말한 방법들에서 더 효율적으로 바뀐 방법이라서 기본 원리는 같을 것이다. 에라토스테네스의 체를 이용한 소수 판별은 그림으로 보면 아주아주 쉽게 이해된다. 아래 애니메이션을 보자.

√N 이하까지 k의 배수들을 모두 제외시킨 나머지가 소수가 된다.
이 때 4부터 시작하는 모든 짝수들은 k=2일 때 제외가 됐으므로 연산할 필요가 없다.

체에 걸러내는 시간 복잡도만해도 O(N log N)이며, 이미 소수가 아닌 것이 확정된 숫자는 검사 대상에서 제외되기 때문에 시간복잡도가 O(N log(log N))이라고 한다. (자세한 설명은 너무 수학적이므로 생략함. 사실 내가 모른다)

---

 

소수 판별의 개념 설명은 여기서 끝이다.
주어진 문제는 소수 판별 뿐만 아니라 범위가 입력받은 M부터 N이어야 하고, 그 안의 소수들을 모두 더한 값과 최소값까지 출력해야 한다.
사실 소수 판별만 됐으면 나머지는 어렵지 않다.

 

사실 소수를 판별하는 방법으로 세 가지를 설명했지만, 정작 문제는 모든 숫자로 나누어떨어지는지 확인하는 방법으로 풀었다. 에라토스테네스 체를 어떻게 코드로 구현하는지가 떠오르지 않았기 때문에 .. 나중에 도전해봐야 할 것 같다.

---

[Pseudocode]

1. 배열 리스트 prime 선언
2. 정수 M 입력 // M 이상
3. 정수 N 입력 // N 이하
4. for i=M 부터 N까지 반복
    5. boolean isPrime = true
        6. if (i <= 1)
            7. continue;
        8. for j=2 부터 i까지 반복
            9. if (i % j == 0)
                10. isPrime = false;
                11. break
        12. if (isPrime)
            13. prime에 i 추가

    14. if (prime이 비어있으면)
        15. -1 출력
    15. else (prime이 비어있지 않으면)
        16. int sum = 0
        17. iterator 선언
        18. while (다음 값이 없을 때까지 반복)
            19. sum += iter.next()

        20. sum 출력
        21. prime의 첫 번째 값 출력

---

[Code]

import java.util.*;

/**
 * 백준 2581번
 * 소수
 * 분류 : 수학, 정수론, 소수 판정
 */
public class Problem12 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        ArrayList<Integer> prime = new ArrayList<>();
        int M = input.nextInt(); // M 이상
        int N = input.nextInt(); // N 이하

        for(int i=M ; i<=N ; i++) {
            boolean isPrime = true;
            if(i <= 1)
                continue;
            for(int j=2 ; j<i ; j++) {
                if(i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                prime.add(i);
            }
        }

        if(prime.isEmpty())
            System.out.println(-1);
        else {
            int sum = 0;
            ListIterator<Integer> iter = prime.listIterator();
            while (iter.hasNext())
                sum += iter.next();

            System.out.println(sum); // 합
            System.out.println(prime.get(0)); // 최소값
        }
        input.close();
    }
}

---

[Result]

---

(2021.07.23 풀이분)