[Java] 백준 1929. 소수 구하기

문제

문제 바로가기

풀이

• 흔히 생각하는 m부터 n까지 각 수에 약수를 하나하나 검사하면 O^2
  • 최악의 경우 1,000,000^2 의 시간복잡도를 가짐으로 시간 초과

나는 아래 두가지 방법을 문제에 적용시킴

1. 에라토스테네스의 체
   • 에라토스네스의 체: 각 수를 검사하면서, 해당 수의 배수를 지움
     • 이럴 경우 검사해야 하는 수가 줄어듬
2. 제곱근 까지만 검사
   • 어떤 수에 대해서, 그 수의 약수는 대칭 쌍을 가짐
     • ex) 12에 대하여: 26, 62(대칭) / 34, 43(대칭)/
       • 이때 대칭쌍을 이루기 때문에 소수를 판별 할 때는 대칭 쌍을 이루는 두 수 중 하나에 대해서만 검사하면 됨
     • ex) 12에 대해, 2*6을 검사할 경우, 12약수에 2를 포함하는지만 검사하면 6은 자연히 따라옴, 즉 2만 검사하면 됨
       • 이때 대칭쌍을 이루는 두 수 중, 하나는 검사하는 수의 제곱근 보다 작고, 다른 하나는 제곱근 보다 큼
       • 즉 임의의 수가 소수인지 판별할 때, 그 수의 제곱근 까지만 검사하면 됨

이 두가지 방법을 응용하여 문제를 풀었다.

• n까지의 인덱스를 가지는 1차원 배열에 소수 여부를 표현(인덱스로 특정 수를 빠르게 검색하기 위해, 1차원 배열로 표현)
• m부터 n까지의 수에 대해 아래의 동작 수행
  • 검사하는 수의 배수들을 소수 후보에서 제외
  • 검사하는 수의 제곱근까지 수들로 나누어 떨어지는지 검사, 소수 판별

코드

// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;

// Please name your class Main
class Main {
    public static void main (String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int m = in.nextInt();
        int n = in.nextInt();

        if (m == 1) m = 2;

        boolean[] arr = new boolean[n+1];   // false: 소수, true: !소수

        for (int i=m; i<=n; i++){

            // i의 배수 처리
            for (int j=i*2; j<=n; j += i){
                arr[j] = true;
            }

            // i의 약수가 존재하는 경우
            if (arr[i]) continue;

            // i가 소수인지 체크
            boolean check = false;
            for (int j=2; j<=Math.sqrt(i); j++){
                if (i%j == 0)   {
                    check = true;
                    break;
                }
            }

            // i가 소수인 경우 처리
            if (check)   arr[i] = true;
        }

        // 출력
        for (int i=m; i<=n; i++){
            if (!arr[i]) bw.write(i + "\n");
        }

        bw.flush();
    }
}

결과

ps

• 회사 면접 중 알고리즘 문제에서, 해당 풀이를 떠올리지 못함..
• 에라토스네스의 체 방법은 면접 피드백을 통해 처음 알았고, 제곱근까지만 검사하는 방법은 이전에도 알고 있었는데 떠올리지 못함
  • 아마 왜 제곱근까지만 검사해도 되는지 확실하게 이해하지 못하고 문제를 풀었던 것 같음..