21.07.28 기록

• 백준 알고리즘 1929 풀이

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

    에라토스테네스의 체로 소수를 구한 후 범위 내의 소수를 출력했다.
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class B1929 {
      public static boolean[] isPrime;
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          StringBuilder sb = new StringBuilder();
  
          int M = Integer.parseInt(st.nextToken());
          int N = Integer.parseInt(st.nextToken());
  
          isPrime = new boolean[N+1];
          getPrime();
  
          //소수만 sb에 저장하기
          for(int i = M; i <= N; i++) {
              if(!isPrime[i]) { sb.append(i).append("\n"); }
          }
  
          System.out.println(sb);
      }
  
  
      //에라토스테네스의 체 - 소수 판별하기
      public static void 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;
              }
          }
      }
  }
  
  

  
  

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

    아래 방법은 소수인지 아닌지 판별과 동시에 소수일 경우 바로 출력을 하는 방법이다.
    

    아래 방법은 최댓값의 제곱근이 아닌, 최댓값까지 순회해야 가능한 방법이다.
    

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
  
   public class B1929 {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
  
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
           int M = Integer.parseInt(st.nextToken());
           int N = Integer.parseInt(st.nextToken());
  
           boolean[] prime = new boolean[N+1];
  
           for(int i = 2; i <= N; i++) {
               if(prime[i]) { continue; }
               if(i >= M) { sb.append(i).append("\n"); }
  
               //i의 배수 인덱스에 true값을 준다.
               for(int j = (i+i); j <= N; j += i) {
                   prime[j] = true;
               }
           }
           System.out.println(sb);
       }
   }