21.07.27 기록

• 백준 알고리즘 11653 풀이

  • 나의 풀이(메모리 27.1MB, 시간 236ms로 통과)
    

    에라토스테네스의 체로 소수를 구한 후 소인수 분해를 했다.
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B11653 {
  
      public static boolean[] isPrime;
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
  
          //N이 1이면 아무것도 출력하지 않는다.
          if(N == 1) { return; }
  
          //1. 에라토스테네스의 체로 소수를 구한 후, 소수 개수 크기의 배열(prime)을 선언한다.
          isPrime = new boolean[N+1];
          int len = getPrime(); //소수의 개수
          int[] prime = new int[len];
  
          //2. 소수만 prime 배열에 저장한다.
          int k = 0;
          for(int i = 0; i < isPrime.length; i++) {
              if(!isPrime[i]) { prime[k++] = i; }
          }
  
          //3. N을 prime 배열의 값으로 소인수 분해한다.
          StringBuilder sb = new StringBuilder();
          int index = 0;
          while(index < prime.length) {
              if(N % prime[index] == 0) { //분해될 때
                  N /= prime[index];
                  sb.append(prime[index]).append("\n");
              } else { index++; }
          }
          System.out.println(sb);
      }
  
      //에라토스테네스의 체 - 소수에 false값을 준 후, 소수 개수를 retrun 한다.
      public static int getPrime() {
          isPrime[0] = true;
          isPrime[1] = true;
  
          for(int i = 2; i <= Math.sqrt(isPrime.length); i++) {
              if(isPrime[i] == true) { continue; }
              for(int j = (i*i); j < isPrime.length; j+=i) {
                  isPrime[j] = true;
              }
          }
  
          int cnt = 0;
          for(int i = 0; i < isPrime.length; i++) {
              if(!isPrime[i]) { cnt++; }
          }
          return cnt;
      }
  }
  
  

  
  

  • 해설 (메모리 14.1MB, 시간 124ms로 통과)
    

    소인수분해란 소수인 인수로 분해하는 것으로 현대 암호학의 기본 토대가 된다.
    (소인수분해를 일률적으로 구할 수 있는 방법을 발견하지 못했기 때문)
    

    배열로 소수를 따로 구할 필요 없이, Math.sqrt(N) 범위 내에서 N을 분해하면 됐다.
    

  
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
  
   public class B11653 {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
  
           int N = Integer.parseInt(br.readLine());
  
           for(int i = 2; i <= Math.sqrt(N); i++) {
               while(N % i == 0) {
                   sb.append(i).append("\n");
                   N /= i;
               }
           }
  
           //남은 N이 소수일 때
           if(N != 1) { sb.append(N); }
           System.out.println(sb);
       }
   }