[BOJ] 1929 _ Java

📝 Problem

: BOJ 1929 소수 구하기

시간 제한	메모리 제한
2초	256 MB

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

💡 Idea

소수를 판정하는 함수를 구현하여, m부터 n까지의 숫자에 대한 결과 출력

1. 소수 판정 함수 구현
   • 함수 내에서 소수이면 해당 숫자 출력
2. main 문에서 for문을 통해 함수 호출

=> 시간 초과 발생

수의 범위가 100만이고, 모든 숫자가 2부터 자기자신까지 루프를 돌아야 하기 때문에 제한 시간을 초과한다.

✔ 코드 (시간 초과)

- 시간복잡도 O(N^2)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
 public static void checkPrimeNum(int x){
     if(x<2){
         return;
     }
     for(int i=2; i<=x/2; i++){
         if(x%i == 0)
             return;
     }
     System.out.println(x);
 }

 public static void main(String[] args) throws IOException{
     BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
     StringTokenizer st = new StringTokenizer(bf.readLine());
     int m, n;
     m = Integer.parseInt(st.nextToken());
     n = Integer.parseInt(st.nextToken());
     System.out.println(m+" " + n);
     if(m>n){
         System.out.println("M is bigger than N");
         return;
     }

     for(int i=m; i<=n; i++)
         checkPrimeNum(i);
 }
}

---

🔍 Learn & Solution

- Learn

   에라토스테네스의 체

에라토스테네스의 체는 N까지의 범위에 속한 모든 소수를 찾는 방법으로, 시간복잡도는 O(N*log(log(N)))이다.

📌 알고리즘

• ex) 100까지의 숫자 중 소수 구하기

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓰고, 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓰고, 자기 자신을 제외한 3의 배수를 모두 지운다,
4. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓰고, 자기 자신을 제외한 5의 배수를 모두 지운다.
5. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓰고, 자기 자신을 제외한 7의 배수를 모두 지운다.
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11^2 > 100이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

=> 4, 8, 10은 2의 배수, 6, 9은 3의 배수로 이미 지워졌기 때문에 생략된다.

* 추가 참고 글 : 백준 FAQ
-> 숫자의 제곱근까지만 나누어보는 방법도 있다.

- Solution

범위 : [m, n]

1. 크기가 n+1인 배열 선언 및 자연수 1이 소수가 아님을 표기
2. 2부터 n까지. 각 수의 배수에 해당하는 수를 제거
   • 이미 지워진 수는 생략
   • 자기 자신 제외, 배수가 n보다 작거나 같을 때까지
3. m 이상, n 이하의 수 중 소수인 수 출력
   
   

1. 크기가 n+1인 배열 선언 및 자연수 1이 소수가 아님을 표기

크기가 n+1인 이유는 인덱스가 0부터 시작하기 때문이고, 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 의미하므로 1은 대상에서 제외시킨다. 이 때, 소수가 아닌 수를 1로 표시한다. 즉, 최종 배열의 0인 값을 가지는 수가 소수가 된다.

2. 2부터 n까지. 각 수의 배수에 해당하는 수를 제거 ★

배열 값을 확인하여 이미 지워진 수는 생략한다. 이 과정을 진행하는 모든 수는 자기 자신 제외하고, 배수가 n보다 작거나 같을 때까지 모든 배수에 대하여 1로 표기(= 소수가 아님)한다.

3. m 이상, n 이하의 수 중 소수인 수 출력

위 과정을 모두 마친 후의 배열에서, 값이 0에 해당하는 인덱스 값이, 2 이상 n 이하의 범위에 속하는 소수이다. 문제에서 주어진 m 이상, n 이하에 대하여 값을 검사하고, 0이면 출력한다.

=> 범위 내의 소수를 모두 출력한다.

---

💻 Code

// 소수 구하기
// M 이상 N 이하의 소수 모두 출력

// 에라토스테네스의 체

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class BJ_1929 {
  public static void main(String[] args) throws IOException{
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(bf.readLine());
      int m, n;
      m = Integer.parseInt(st.nextToken());
      n = Integer.parseInt(st.nextToken());
      bf.close();

      if(m>n){
          System.out.println("M is bigger than N");
          return;
      }

      /* arr[i]의 값이 0이면 소수 */
      int[] arr = new int[n+1];
      arr[1] = 1; // 1은 소수가 아님.

      for(int i=2; i<=n; i++){ // 숫자 i에 대하여 소수 여부 저장
          if(arr[i] != 1)
              for(int j=2; i*j<=n; j++){ // 범위 내에서, 소수가 아닌 수 1로 저장
                  arr[i*j] = 1;
              }
      }

      for(int j=m; j<=n; j++)
          if(arr[j] != 1)
              System.out.println(j);

  }
}

---