[JAVA] 약수, 배수와 소수 2

1934 최소공배수

유클리드 호제법이란?

•  a와 b의 최대공약수를 gcd(a,b)라 할 때, gcd(a,b) == gcd(b,r)이다. r은 a%b이다.
• a%b == 0 이라면 gcd(a,b) == b가 될 것이다. 이때까지 위 식을 반복한다.
• 유클리드 호제법을 이용하여 최대공약수를 구한 후, a*b에 최대공약수를 나누면 최소공배수가 나온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int n = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();

      for(int i=0;i<n;i++){
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int c = gcd(a, b);
        sb.append(a*b/c).append("\n");
      }
      System.out.println(sb);
      
    }
  public static int gcd(int a, int b) {

    while (b != 0) {
      int r = a % b; // 나머지를 구해준다.

      // GCD(a, b) = GCD(b, r)이므로 변환한다.
      a = b;
      b = r;
    }
    return a;
  }
}

 

 

---

13241 최소공배수

int형을 Long으로 바꾼것 말고 다른 점 없음

 

---

1735 분수 합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    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 a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(br.readLine(), " ");
      int c = Integer.parseInt(st.nextToken());
      int d = Integer.parseInt(st.nextToken());

      int up = (c*b+a*d);
      int down = (b*d);
      int gcd = gcd(up,down);

      System.out.println((int)up/gcd + " " + (int)down/gcd);
      
    }
  public static int gcd(int a, int b) {

    while (b != 0) {
      int r = a % b; // 나머지를 구해준다.

      // GCD(a, b) = GCD(b, r)이므로 변환한다.
      a = b;
      b = r;
    }
    return a;
  }
}

정석대로 분수합 구하고 gdc로 약분해주기

 

---

2485 가로수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      StringBuilder sb = new StringBuilder();

      int a = Integer.parseInt(br.readLine());
      int[] num = new int[a];

      for(int i=0;i<a;i++){
        num[i]=Integer.parseInt(br.readLine());
      }
      Arrays.sort(num);
      int gcd=0;
      
      for(int i=0;i<a-1;i++){
        int distance=num[i+1]-num[i];
        gcd = gcd(distance,gcd);
      }
      System.out.println((num[a-1]-num[0])/gcd+1-(num.length));
      
      
    }
  public static int gcd(int a, int b) {

    while (b != 0) {
      int r = a % b; // 나머지를 구해준다.

      // GCD(a, b) = GCD(b, r)이므로 변환한다.
      a = b;
      b = r;
    }
    return a;
  }
}

가로수 간격들의 최대공약수를 구한다.

심어진 가로수의 (최대 위치 - 최소 위치)/최대공약수 +1 은 전체 가로수의 수가 된다.

우리가 심을 가로수는 전체 가로수에서 심어진 가로수의 수 를 빼서 구한다.

 

---

4134 다음 소수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Arrays;

public class Main {
    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=0;i<n;i++){
        Long a = Long.parseLong(br.readLine());
        if(a == 0 || a == 1 || a == 2)
        {
            System.out.println(2);
            continue;
        }

        while(true)
        {
            int result = 0;
            for(long j=2; j<=Math.sqrt((double)a); j++)
            {
                if(a % j == 0)
                {
                    result++;
                    break;
                }
            }

            if(result == 0)
            {
                System.out.println(a);
                break;
            }

            a++;
        }
      
    }
  }
}

일단 4*10^9 라는 입력 조건이 있으니 Long 타입으로 입력받아야 한다.

소수 판별을 위해 입력받은 수 n까지 확인하는 것은 오래 걸리므로 n의 제곱근까지만 확인한다.

소수를 판별하기 위해 약수로 나누어 떨어지는지 확인하는데, 약수는 대칭적인 형태를 이루기 때문이다.

또 Math 함수를 사용할 때 수를 double로 바꾸어야지 큰 수에서 오차가 나지 않는다!

 

---

1929 소수 구하기

에라토스테네스의 체를 이용하기.

k=2 부터 √N 까지 반복하여 자연수중 k를 제외한 k의 배수를 지운다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Arrays;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      int m = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());

      prime = new boolean[n + 1];
      get_prime();

      StringBuilder sb = new StringBuilder();

      for(int i = m; i <= n; i++) {
        // false = 소수 
        if(!prime[i]) sb.append(i).append('\n');
      }
      System.out.println(sb);
      
      
    }
  public static void get_prime() {
    // true = 소수아님 , false = 소수 
    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;
      }
    }
  }
}

boolean 배열을 선언은 일반 배열과 같게 하면된다. default값은 false이다.

get_prime() 함수에서 Math.sqrt를 이용하여 제곱근까지만 소수를 구하고, 이중 for문으로 소수의 배수들은 모두 true로 바꾸어준 것을 주목하자.

 

---

4948 베르트랑 공준

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Arrays;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      prime = new boolean[123456*2+1];
      get_prime();

      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++;
        }

        System.out.println(cnt);
      }
      
      
    }
  public static void get_prime() {
    // true = 소수아님 , false = 소수 
    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;
      }
    }
  }
}

 

---

17103 골드바흐 파티션

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//import java.util.Arrays;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());

      prime = new boolean[1000001];
      get_prime();

      for (int i=0;i<n;i++){
        int a = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int j=2;j<a/2+1;j++){
          if (!prime[j] && !prime[a-j]) cnt++;
        }
        System.out.println(cnt);
      }
      
      
    }
  public static void get_prime() {
    // true = 소수아님 , false = 소수 
    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;
      }
    }
  }
}

소수는 false이고, 순서다른 소수는 같은 파티션임을 기억하자.

j와 입력받은 수 a-j 모두 소수이면 파티션이다.

 

---

13909 창문 닫기

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int count = 0; //창문이 열려있는 개수
        for(int i = 1; i * i <= N; i++) { //제곱수만 카운트
            count++;
        }

        bw.write(count + "\n");

        br.close();

        bw.flush();
        bw.close();
    }


}

설명이 복잡하지만 결국 N까지 진행을 하였을 때 마지막에 열린 창문의 개수를 구한다.

N까지의 수 중 약수의 개수가 홀수인 경우에만 마지막에 열리게 된다.

약수의 개수가 홀수인 수는 제곱수밖에 없으니, N까지의 수 중 제곱수를 구하는 문제이다!

 

---

# 회고

 

스택, 큐, 덱 단계만 남았다!

이전에 파이썬으로 백준을 풀때보다 문제가 늘어난 단계이다..게다가 못푼 문제도 있음.