21.07.23 기록

• 백준 알고리즘 1978 풀이

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

    나름 규칙을 찾아보려했지만, 반례가 항상 있어서 그냥 for문으로 풀이했다.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class B1978 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          br.readLine();  //testCase 개수. 쓰지 않기 때문에 변수에 저장하지 않았다.
  
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          int count = 0;
  
          while(st.hasMoreTokens()) { //token이 있는 동안 반복
              int num = Integer.parseInt(st.nextToken());
              boolean isPrime = true;  //소수이면 true 값을, 소수가 아니면 false 값을 가진다.
  
              if(num == 1) { continue; } //1은 소수가 아니다.
  
              for(int i = 2; i < num; i++) { //1과 자기자신 제외
                  if(num % i  == 0) { //나눠지는 수가 있으면 소수가 아니다.
                      isPrime = false;
                      break;
                  }
              }
              if(isPrime) { count++; }
          }
          System.out.println(count);
      }
  }
  

  
  

  해설 참조

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

    num을 x, y의 합성수 (num = x * y) 라고 볼 때 (1 <= x, y < num) 과 같은 부등식을 세울 수 있다.
    

    만약 x, y가 num의 제곱근보다 커지면 x, y > sqrt(num) 위의 부등식에 모순이 생긴다.
    

    따라서 x, y중 적어도 하나는 num의 제곱근보다 같거나 작다.
    

    결론적으로 num의 제곱근까지만 검사를 하면 된다.
    

  
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
  
   public class B1978 {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           br.readLine();
  
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
           int count = 0;
  
           while(st.hasMoreTokens()) {
               int num = Integer.parseInt(st.nextToken());
               boolean isPrime = true;
  
               if(num == 1) { continue; }
  
               for(int i = 2; i <= Math.sqrt(num); i++) {
                   if(num % i  == 0) {
                       isPrime = false;
                       break;
                   }
               }
               if(isPrime) { count++; }
           }
           System.out.println(count);
       }
   }
  

  
  

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

    «에라토스테네스의 체»
    

    체를 거르는 듯한 느낌으로 2를 제외한 2의 배수들, 3을 제외한 3의 배수들 등을 걸러 소수만 남기는 방법이다.
    

    해설1을 적용시켜 구하려는 범위(num)의 최댓값의 제곱근까지만 반복하면 된다.
    

    (1)1부터 1000까지의 수에서 소수이면 false 값을 가지는 boolean 배열을 생성한다.
    

    (2)입력값을 boolean 배열의 인덱스로 사용했을 때 그 값이 false이면 소수로 count를 한다.
    

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
  
   public class B1978 {
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           br.readLine();
  
           //1. 크기가 1000 + 1인 boolean 배열 선언
           final int MAX = 1000;
           boolean[] prime = new boolean[MAX+1];
  
           //2. 소수가 아니면 true, 소수이면 false을 가진다.
           prime[0] = true;
           prime[1] = true;
  
           //3. 소수가 아닌 값은 true로, 소수는 false로 남겨 놓기
           for(int i = 2; i <= Math.sqrt(MAX); i++) {
               if(prime[i] == true) { continue; }
  
               for(int j = (i*i); j < (MAX+1); j += i) {
                   prime[j] = true;
               }
           }
  
           //4. 소수만 카운트해서 count값을 출력한다.
           int count = 0;
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
           while(st.hasMoreTokens()) {
               int num = Integer.parseInt(st.nextToken());
  
               if(!prime[num]) { count++; }
           }
           System.out.println(count);
       }
   }