주어진 숫자 범위 내 소수 구하기(에라토스테네스의 체)

개요

알고리즘 글을 작성 하기에 앞서, 사실 요즘 워낙 좋은 세상이여서 GPT를 사용하면 대략적인 알고리즘을 해결할 수 있고, 특히 Spring을 활용한 다양한 프로젝트에서 생성형 ai를 많이 사용하는 바, 이러한 알고리즘 풀이가 크게 도움이 될까 생각이 든다.
그러나 나의 굳어버린 뇌를 활성화 하기 위해 GPT에 의존하지 않고 알고리즘을 하나씩 풀어보고, 무엇보다 어려운 수학문제를 푸는 재미와 어떻게 이런 생각을 했지라는 감탄을 얻기 위해 알고리즘 문제를 하나씩 풀어나가겠다.

그 처음문제가 바로 주어진 숫자 범위 내 소수 구하기 이다.

소수란?

소수란 1과 자기자신만으로 나눠지는 수다. 2, 3의 약수는 1과 자기 자신뿐으로 소수가 될 수 있고, 4의 약수는 1, 2, 4이므로 소수가 아니다. 1 또한 소수가 아니다.

접근방법

1부터 10까지의 숫자가 주어 졌을 때 우리는 어떻게 소수를 구할 수 있을까?
가장 쉬운 방법은 숫자를 2부터 하나씩 자기자신 직전의 숫자까지 나눠 봐서 나머지가 0인지 아닌지를 확인 하면 된다.
나는 여기서 하나 더 나아가서 기존의 배수인 숫자들을 0으로 만들어줘 분기에서 탈출하게 했다.

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

public class Main {
public static void main(String[] args) {
ArrayList<Integer> answer = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);

        int start = scanner.nextInt();
        int end = scanner.nextInt();


        for (int i = start; i <= end; i++) {
            answer.add(i);
        }

        for (int i = 0; i < answer.size(); i++) {
            for (int j = 2; j <= end; j++) {
                if (answer.get(i) == 1 || answer.get(i) == 0) {
                    break;
                }
                if (answer.get(i) == j) {
                    System.out.println(answer.get(i));
                    break;
                } else if (answer.get(i) % j == 0) {
                    answer.set(i, 0);
                }
            }
        }

    }
}

그래서 처음 접근한 방식은 위와 같다.
1과 100을 입력 했을 때 2만 남겨 놓고 다른 2의 배수를 0으로, 3만 남겨 놓고 다른 3의 배수는 0으로 만들어 줬다.
즉, 소수를 제외한 범위 내 다른 숫자들을 0으로 만들어주고 실제로 값이 있는 것만 뽑아냈다.
그러나 이게 왠걸, 내 로컬환경에서는 결과값을 잘 뽑아 냈지만, 이 상태로 백준에 제출을 하니 시간초과가 나왔다.

그래서 부랴부랴 소수를 구하는 간편한 알고리즘이 무엇이 있는지 확인을 했다.

에라토스테네스의 체

그래서 나왔던게 바로 에라토스테네스의 체이다.
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이라고 해서 이 분의 이름을 따왔다고 한다.
고대 그리스인들이 지금 태어나서 컴퓨터를 배웠다면 어떘을까? 라는 생각을 하게 된다.
나와 달랐던 점은 나는 하나하나 2~99까지 다 나눠주면서 소수를 판별한 것이고, 에라토스테네스는 소수로만 나눠주면서 판별을 한 것이다.
문제 풀기에 급급해서 이 생각을 못한 것이 좀 아쉽다.
그래서 나온 코드는 아래와 같다.

import java.io.*;

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

        String input = br.readLine();
        String[] numbers = input.split(" ");

        int start = Integer.parseInt(numbers[0]);
        int end = Integer.parseInt(numbers[1]);

        boolean[] isPrime = new boolean[end + 1]; // 소수 판별 배열
        java.util.Arrays.fill(isPrime, true); // 모든 숫자를 소수로 가정
        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for (int i = 2; i * i <= end; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= end; j += i) {
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }

        for (int i = start; i <= end; i++) {
            if (isPrime[i]) { // 시작점부터 끝점까지 소수인지 판별 후 출력
                bw.write(i + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
}

사실 처음 시간초과가 나왔을 때 scanner와 sout을 써서 그런가 생각해서 BufferReader와 BufferWriter를 활용 했으나 그것이 답이아니였다.
입력 받은 숫자만틈 Boolean타입 배열을 만들고 그 중에서 소수인것만 끄집어 내는 코드이다.

자세한 내용은 나무위키를 참고하면 된다.
에라토스테네스의 체

마치며

사실 백준에서 시간초과가 나왔을 때 위에 쓴것처럼 Scanner를 써서 그런건가? 해서 이것저것 다 해봤는데, 아니였다.
결국 나의 알고리즘 성능이 너무 아쉬웠던 것....
다음부턴 결과만 내는 것이 아니라 어떻게 하면 더 효율적으로 계산할 수 있을지도 생각해봐야겠다.
끝으로 우리 에라토스테네스 초상화를 넣으면서 마무리 해야겠다.

ps

알고보니 이분 지구의 둘레를 처음으로 계산하셨던 분이었다. 딱히 1등을 하지 않아 별명이 베타였다니...