99클럽 코테 스터디 1일차 TIL + 소수 구하기

https://www.acmicpc.net/problem/1929

 

 

 

- 오늘의 학습 키워드

에라토스테네스의 체 (소수 판별 알고리즘)

- 풀이

M 이상 N 이하의 모든 소수를 출력해야 하기 때문에,
일일이 하나씩 검사하면 시간 초과가 날 수 있어서 효율적인 소수 판별 방법인
에라토스테네스의 체 알고리즘을 사용해야 한다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int M = sc.nextInt(); // 시작 값
        int N = sc.nextInt(); // 끝 값

        // 소수 판별을 위한 배열 (true면 소수라고 가정함)
        boolean[] isPrime = new boolean[N + 1];

        // 초기화 - 2 이상은 모두 소수(true)로 설정
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }

        // M부터 N까지의 숫자 중 소수만 출력
        for (int i = M; i <= N; i++) {
            if (isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

 

풀이 순서

1. boolean[] isPrime 배열을 만들어 0~N까지 소수 여부를 저장
2. 2부터 √N까지 반복하면서, i의 배수를 전부 false 처리
3. M부터 N까지 순회하며 isPrime[i]가 true인 숫자만 출력

 

에라토스테네스의 체는 소수를 빠르게 구하는 대표적인 방법으로, 2부터 시작해서 해당 수의 배수를 지워나가는 방식이다.

 

예를 들어 1부터 10까지의 수에서 소수를 구해보자.
1은 소수가 아니므로 제외하고, 2부터 10까지 살펴본다.

• 2는 소수이므로, 2의 제곱(4)부터 2의 배수들을 지운다 → 4, 6, 8, 10
• 3은 소수이므로, 3의 제곱(9)부터 배수를 지운다 → 9
• 다음 숫자 4는 이미 지워졌으므로 건너뛴다.

이때 우리가 찾고자 하는 수는 10까지이므로, 제곱했을 때 10을 넘지 않는 소수까지만 검사하면 된다.
즉, √10 이하의 소수까지만 배수를 지우면 된다 → 2와 3까지만 체크!

 

결과적으로 지워진 수는 4, 6, 8, 9, 10이고, 남은 수는 2, 3, 5, 7 → 이들이 소수가 된다.
이게 에라토스테네스의 체 방식이다.

 

그리고BufferedReader와 BufferedWriter 사용해서 입출력 속도도 개선해 보았다.

위에서 부터 이 순서로 해본 결과다

1. BufferedReader + BufferedWriter

2. BufferedReader + System.out.println

3. Scanner + System.out.println

 

- 오늘의 회고

처음에는 M부터 N까지 하나하나 소수인지 검사하려고 했는데, 범위가 최대 1,000,000이라서 시간 초과가 날 것 같았다.

그래서 시간 초과를 막기 위해 에라토스테네스 체를 오랜만에 찾아본 다음 시도했다.

소수 판별에는 단순 나눗셈보다 체 알고리즘이 훨씬 빠르다는 걸 체감했다. 이래서 수학 잘하는 사람들이 코테를 잘하는건가..