21.07.29 기록

• 백준 알고리즘 4948 풀이

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

    지난 해설풀이 방법을 사용하여 풀이했다.
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B4948 {
      public static boolean[] prime;
      public static StringBuilder sb = new StringBuilder();
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          while(true) {
              int N = Integer.parseInt(br.readLine());
  
              if(N == 0)  { break; }
              else {
                  prime = new boolean[2*N+1];
                  countPrime(N);
              }
          }
          System.out.println(sb);
      }
  
      public static void countPrime(int N) {
          int count = 0;
          for(int i = 2; i < prime.length; i++) {
              if(prime[i] == true) { continue; }
              if(i > N) { count++; }
  
              for(int j = (i+i); j < prime.length; j+= i) {
                  prime[j] = true;
              }
          }
          sb.append(count).append("\n");
      }
  }
  

  
  

  해설 참조

  • 해설1 (메모리 15.2MB, 시간 204ms로 통과)
    

    이 해설은 (N의 최대 범위 x 2 + 1) 크기의 배열을 선언하여 풀이했다.
    

    내 풀이는 입력 값에 따라 배열 크기를 재지정했다면, 해설 풀이는 한 번 선언한 배열로 풀이를 한 것이다.
    

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
  
   //2. 해설 풀이 (N의 최대 범위 + 1 크기로 배열을 선언한 후 계속 사용)
   public class B4948 {
       public static boolean[] prime = new boolean[2*123456+1];
  
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
  
           getPrime();
           while(true) {
               int N = Integer.parseInt(br.readLine());
               if(N == 0) { break; }
  
               int cnt = 0;
               for(int i = (N+1); i <= (2*N); i++) {
                   if(!prime[i]) { cnt++; }
               }
               sb.append(cnt).append("\n");
           }
           System.out.println(sb);
       }
  
       public static void getPrime() {
           prime[0] = prime[1] = true;
  
           for(int i = 2; i <= Math.sqrt(prime.length); i++) {
               if(prime[i]) { continue; }
               for(int j = (i*i); j < prime.length; j+=i) {
                   prime[j] = true;
               }
           }
       }
   }
  

  
  

  • 해설2 (메모리 15.5MB, 시간 148ms로 통과)
    

    해설2는 입력값마다 소수의 개수가 몇 개 인지 센 배열을 하나 더 추가하였다.
    

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
  
   public class B4948 {
       public static final int MAX_VALUE = (2 * 123456) + 1;
       public static boolean[] prime = new boolean[MAX_VALUE];
       public static int[] cntPrime = new int[MAX_VALUE];
  
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
  
           getPrime();
           countPrime();
           while(true) {
               int N = Integer.parseInt(br.readLine());
  
               if(N == 0) { break; }
               sb.append(cntPrime[2*N] - cntPrime[N]).append("\n");
           }
  
           System.out.println(sb);
       }
  
       public static void getPrime() {
           prime[0] = prime[1] = true;
  
           for(int i = 2; i <= Math.sqrt(prime.length); i++) {
               if(prime[i]) { continue; }
               for(int j = (i*i); j < prime.length; j+=i) {
                   prime[j] = true;
               }
           }
       }
  
       public static void countPrime() {
           int cnt = 0;
           for(int i = 2; i < prime.length; i++) {
               if(!prime[i]) { cnt++; }
               cntPrime[i] = cnt;
           }
       }
   }