[알고리즘]소수 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.Objects;
import java.util.StringTokenizer;

/* *
 *
 *
 *
 *
 *
 *
 *  */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        for (int i = m; i <= n; i++) {
            Number number = new Number(i);
            if (number.isPrimeNumber()) {
                System.out.println(number.getValue());
            }
        }
    }
    
    public static class Number {
        private final int value;
        
        public Number(int value) {
            //입력조건 제한
            if (!(1 <= value && value <= 1000000)) {
                String errorMessage = MessageFormat.format("value =>{0} 는 1 이상 1,000,000 이하여야 합니다.", value);
                throw new IllegalArgumentException(errorMessage);
            }
            this.value = value;
        }
        
        // 해당 객체에 대한 소수 판별을 수행합니다.
        public boolean isPrimeNumber() {
            // 1 은 소수가 될 수 없으며,
            if (this.value == 1) {
                return false;
            }
            //2 부터 this.value 의 직전값까지 중에
            for (int i = 2; i < this.value; i++) {
                //정확하게 나눠떨어지는 값이 존재하는 경우에는 소수가 아닙니다.
                if (this.value % i == 0) {
                    return false;
                }
            }
            
            return true;
        }
        
        //getter
        public int getValue() {
            return value;
        }
    }
    
}

• 기존의 코드이다.

• 그대로 제출 했는데 시간 초과가 발생했다.

추측

1. 혹시 m 값의 범위가 1,000,000 까지라서 출력하는 프린트문이 너무 많아서 생긴 문제인지 확인하였다.
   • 일단 System.out.println 의 효율성에 대해 간략하게 논해보겠다.
     • 개요
       • 콘솔 출력을 위해 알고리즘에서 주로 사용되는 메서드
     • 효율성 문제
       • System.out.println 의 경우 버퍼링(Buffering) 을 수행하지 않습니다.
       • 그래서.. 매번 println 호출시 마다 I/O 작업이 수행되므로, 매우 비효율적입니다.
     • 대안
       • 버퍼링을 사용해야합니다.
         • BufferWriter 혹은 PrintWriter 등의 클래스를 사용해 IO 작업의 빈도를 줄이고 출력을 버퍼링해야합니다.
   • PrintWriter의 경우 텍스트 출력을 위한 편리한 API 가 내장되어있습니다.
   • 자체적으로 버퍼링 기능은 존재하지 않지만,
     • print() , println() 등의 기능을 사용할 수 있습니다.
     • autoFlush 라는 특수한 기능도 가지고 있기에, 메서드 수행시마다 flush 에 대한 고려를 하지 않도록 개발자 편의적인 API 입니다.
   • PrintWriter 와 BufferWriter 둘다 사용을 해보도록 하겠습니다.
     • PrintWriter 는 인자에 Writer 를 받기에, BufferWriter 와 조합이 가능합니다.

   public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           //버퍼링 기능 + 개행문자를 자동으로 추가해주는 기능을 가진 PrintWriter 를 사용합니다.
           PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
           StringTokenizer st = new StringTokenizer(br.readLine()," ");
           int m = Integer.parseInt(st.nextToken());
           int n = Integer.parseInt(st.nextToken());
           
           for (int i = m; i <= n; i++) {
               Number number = new Number(i);
               if (number.isPrimeNumber()) {
                   pw.println(number.getValue());
               }
           }
       }

   • 시간초과 가 여전히 발생합니다. 근본적인 로직의 문제같습니다.

2. 소수 구하기의 공식같은 에라토스테네스의 체 관련 문제이다.
   • 시간초과 가 출력속도의 문제는 아니였습니다.
   • 일단 기존로직은 O(n^2) 의 시간복잡도를 가지고 있다.
   • 본 공식을 이용해 O(n) 의 시간복잡도로 줄일 수 있다.
   • 에라토스테네스의 체
     • 2 부터 N 까지의 숫자를 적습니다.
     • 아직 지워지지 않은 소수중 가장 작은 숫자를 선택하면 2 가 됩니다. 해당 숫자의 배수는 2를 제외하고는 항상 소수가 될 수 없습니다.
     • 항상 2 라는 약수를 가지기 때문이죠
     • 그리고 그 다음 작은 3 을 선택. 해당 숫자의 배수를 또 전부 제외합니다.
     • 이도 마찬가지로 항상 3 이라는 약수를 모두 가지기 때문입니다.
     • 계속 5 …7 … 이어 나가서 모든 배수를 제외하면
     • 남은 소수만 남게됩니다.
   • 에라토스테네스의 체에 관련 최적화점
     1. 1 은 무조건 소수가 아닙니다.
     2. 2는 유일한 짝수 소수입니다.
        • 2의 배수를 제외하면
        • 2 제외 전부 홀수만 약수의 후보가 될 수 있습니다.
     3. 3부터 시작하여 배수가 될 수 있는 검사 대상 값 의 제곱근까지가

        검사 대상을 나눌 수 있다면 ⇒ 소수 아님

        끝까지 검사가 통과한다면 ⇒ 소수임

     4. 또한 홀수만 검사하면 되기에, 반복문은 3부터 시작하여 2씩 증가시킴으로 기존 반복문보다 더 적은 반복 횟수를 가지게 됩니다.

3. 최종 통과 로직

    package org.example.소수구하기;
   
   import java.io.*;
   import java.text.MessageFormat;
   import java.util.Objects;
   import java.util.StringTokenizer;
   
   public class Main {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           // 버퍼링 기능 + 개행문자를 자동으로 추가해주는 기능을 가진 PrintWriter 를 사용합니다.
           // + flush 시점을 제가 제어하고 싶기에 별도 autoflush 설정을 하지 않았습니다.
           // autoFlush 를 하는 경우 api 수행시마다 flush 가 발생합니다. 이는 성능에 영향을 미칠 수 있습니다.( 사소하겠지만 )
           PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
           int m = Integer.parseInt(st.nextToken());
           int n = Integer.parseInt(st.nextToken());
           
           for (int i = m; i <= n; i++) {
               Number number = new Number(i);
               if (number.isPrimeNumber()) {
                   pw.println(number.getValue());
               }
           }
           pw.flush();
       }
       
       public static class Number {
           private final int value;
           
           public Number(int value) {
               // 입력조건 제한
               if (!(1 <= value && value <= 1000000)) {
                   String errorMessage = MessageFormat.format("value =>{0} 는 1 이상 1,000,000 이하여야 합니다.", value);
                   throw new IllegalArgumentException(errorMessage);
               }
               this.value = value;
           }
           
           // 해당 객체에 대한 소수 판별을 수행합니다.
           public boolean isPrimeNumber() {
               //? 에라토스 테네스의 채 로직 적용
               // ! 1 은 제외합니다.
               if (this.value == 1) {
                   return false;
               }
               // ! 2 는 유일한 짝수 소수입니다. 2의 배수값을 전부 제외합니다 ( 짝수 숫자가 모두 제외됩니다)
               if (this.value != 2 && this.value % 2 == 0) {
                   return false;
               }
               //!홀수만 체로 걸러집니다. 3부터 시작해서 제곱근까지만 검사합니다.
               for (int i = 3; i <= Math.sqrt(this.value); i += 2) {
                   //나눠지는 값이 존재하면 소수가 아닙니다.
                   if (this.value % i == 0) {
                       return false;
                   }
               }
   
               return true;
           }
           
           // getter
           public int getValue() {
               return value;
           }
       }
       
   }

4. 변수명 리팩토링
   • 변수명 Number 클래스의 개념을 가진 number 인스턴스가 추상화의 의미상 맞지 않다고 생각했습니다.

     인스턴스 vs 객체 인스턴스는 그 객체가 메모리에 할당되어 실제 사용되는 경우 객체는 클래스의 타입으로 선언되었을때 객체라고 명명

   • number 명을 자연수의 의미를 가진 naturalNumber 로 수정했습니다.

   for (int i = m; i <= n; i++) {
               Number naturalNumber = new Number(i);
               if (naturalNumber.isPrimeNumber()) {
                   pw.println(naturalNumber.getValue());
               }
           }

Uploaded by N2T