[Java]백준 2581번: 소수

문제 url:
소수

문제:

🤔 문제 알아보기

• 이전에 풀었던 소수문제에 살짝 조건이 추가된 문제이다.
• 소수 푸는 해석이 필요하면 아래 주소로 이동해서 소수에 대해서 알아보면 좋을듯 하다
  • 소수 해석 풀이
• 먼저 최소값 M과 최댓값 N을 두 줄을 걸처 입력 받는다.
• 그 후 합계와 최솟값을 출력하는데, 만일 소수가 없다면 -1을 출력한다.
• 여기서 최댓값 N을 필자는 Max로, 최솟값 M을 min으로 지칭하여 설명하면,
  • max값에 해당하는 자리까지 소수를 구한 다음
  • 반복문을 통해 min ~ max에 해당하는 소수를 구한후 누적합을 구하면 된다.
  • 최솟값을 출력할 때에는 제일 먼저 나오는 값이 최솟값이므로
  • 의문문을 통해 최솟값이 0과 같으면 첫번 째 수를 넣고 그 후는 해당 로직이 되지 않도록 하면 될 것같다.

😎 준비하기

이번에는 이전 시간에 배운 에레토스테네스의 체를 이용해 소수를 구해보도록 하겠다.

🐱‍👤 실제 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int min = Integer.parseInt(br.readLine());
        int max = Integer.parseInt(br.readLine());

        //최솟값, 합계 변수 정의
        int sum = 0;
        int min_num = 0;

        // 함수 호출
        boolean[] prime_num = makePrimeNum(max);

        // 최솟값과, min과 max사이의 소수를 불러올 차례
        for (int i = min; i < max + 1; i++) {
            if (!prime_num[i]) {
                sum += i;

                if(min_num == 0) {
                    min_num = i;
                }
            }
        }

        if(sum != 0) {
            System.out.println(sum);
            System.out.println(min_num);
        }  else {
            System.out.println(-1);
        }

    }

    public static boolean[] makePrimeNum(int max) {
        //에라토스테노스의 체로 문제를 풀어보도록 하자.
        // 0부터 체에 거를꺼기 때문에 max + 1을 설정
        boolean[] prime_num = new boolean[max + 1];

        //0과 1은 소수가 아니므로 true를 주어 체에 걸려졌음을 설정
        prime_num[0] = true;
        prime_num[1] = true;

        for(int i = 2; i <= Math.sqrt(max); i++) {

            // 이미 해당 숫자가 소수가 아니라 체에 걸러지면 위로 이동
            if(prime_num[i]) {
                continue;
            }

            // 에레토스테네스 체에 해당하는 알고리즘
            // 원래는 i * 2를 하는 것이 정석이나 위에서 2는 false로 걸러졌기 때문에 
            // 해당 배수의 가장 작은 값은 i * i
            // j는 max+1을 한 이유는 prime_num에는 0도 배열에 포함되어 있기에 +1한 것
            // j + i를 하게 되면 이제 i의 배수가 j에 들어가 해당 값을 체에 거르도록 함
            for(int j = i * i; j < max+1; j = j + i) {
                prime_num[j] = true;

            }

        }

        return prime_num;
    }

}

소수를 구하면 그 이후는 특별히 어려운 점이 없다고 생각한다.

✨ 에레토스테네스의 체 말고 다른 방법으로 소수 구하기

이전 시간에 배운 코드를 다시 복습하는 마음으로 다시 구해보도록 하겠다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int min = Integer.parseInt(br.readLine());
        int max = Integer.parseInt(br.readLine());

        int sum = 0;
        int min_num = 0;

        List<Integer> prime_num = savePrimeNum(max);

        for(int i = min; i <= max; i++) {
            if (prime_num.contains(i)) {
                sum += prime_num.get(prime_num.indexOf(i));

                if (min_num == 0) {
                    min_num = prime_num.get(prime_num.indexOf(i));
                }
            }
        }

        if (sum != 0) {
            System.out.println(sum);
            System.out.println(min_num);
        } else {
            System.out.println(-1);
        }


    }

    public static List<Integer> savePrimeNum(int max) {
        List<Integer> prime_num = new ArrayList<>();

        for (int i = 2; i <= max; i++) {
            boolean notPrime = false;

            for (int j = 2; j <= Math.sqrt(max); j++) {
                if(i % j ==0) {
                    notPrime = true;
                    break;
                }

            }
            if(notPrime == false) {
                prime_num.add(i);
            }
        }

        return prime_num;

    }
}

역시 주어진 수가 존재하지 않고 N번쨰까지의 소수를 구할 때에는 에레토스테네스의 체를 사용하는 것이 더 바람직하고 빠른 방법일 수 있을것 같다.