21.07.26 기록

• 백준 알고리즘 2581 풀이

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

    지난풀이에서 해설1의 방법을 이용하여 풀이했다.
    

  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B2581 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          int M = Integer.parseInt(br.readLine());
          int N = Integer.parseInt(br.readLine());
          boolean[] isPrime = new boolean[N-M+1]; //범위의 +1한 크기로 배열을 선언한다.
  
          //1은 소수가 아니다.
          if(M == 1 || N == 1) { isPrime[0] = true; }
  
          //1. 소수가 아닌 인덱스에 true 값을 준다.
          for(int i = M; i <= N; i++) {
              for(int j = 2; j <= Math.sqrt(i); j++) {
                  if(i % j == 0) { //나누어 떨어질 때 소수가 아니다.
                      isPrime[i-M] = true;
                      break;
                  }
              }
          }
  
          //2. 모든 소수의 합과 최소값을 구한다.
          int sum = 0;
          int min = 0;
          for(int i = 0; i < isPrime.length; i++) {
              if(!isPrime[i]) { //false(소수)값을 가질 때
                  sum += (i+M);
                  if(min == 0) { min = (i+M); }
              }
          }
  
          //3. 소수의 합이 0이면 -1을 출력한다.
          if(sum == 0) {
              System.out.println(-1);
          } else {
              System.out.println(sum + "\n" + min);
          }
      }
  }
  

  
  

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

    내 풀이는 범위 크기의 +1만큼(N-M+1) 배열을 생성하여 풀이했다면,
    해설은 N+1 크기만큼의 에라토스테네스의 체를 사용하여 풀이했다.
    

    첫번째 소수를 구하는 방법으로, 변수 min의 값을 Integer.MAX_VALUE로 초기화 하는 부분에서 또 하나 배웠다!

  
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
  
   //2. 해설 풀이
   public class B2581 {
  
       public static boolean[] prime;
  
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           int M = Integer.parseInt(br.readLine());
           int N = Integer.parseInt(br.readLine());
  
           //인덱스 값이 소수이면 true, 소수가 아니면 false
           prime = new boolean[N+1];
           getPrime();
  
           int sum = 0;
           int min = Integer.MAX_VALUE;
           for(int i = M; i <= N; i++) {
               if(prime[i] == false) {
                   sum += i;
                   if(min == Integer.MAX_VALUE) { min = i; }
               }
           }
  
           if(sum == 0) {
               System.out.println(-1);
           } else {
               System.out.println(sum + "\n" + min);
           }
       }
  
       //에라토스테네스의 체
       public static void getPrime() {
           prime[0] = true;
           prime[1] = true;
  
           for(int i = 2; i <= Math.sqrt(prime.length); i++) {
               if(prime[i] == true) { continue; }
               for(int j = (i*i); j < prime.length; j += i) {
                   prime[j] = true;
               }
           }
       }
   }