본문 바로가기
CT

[BOJ] 15단계 약수, 배수와 소수 2

kinggora 2023. 4. 10. 22:48
1 1934 최소공배수

최대공약수 -> 최소공배수

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

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

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            String[] split = reader.readLine().split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);
            sb.append(a * b / gcd(a,b)).append("\n");
        }
        System.out.print(sb);
    }

    //최대공약수 구하기 - 유클리드 호제법
    public static int gcd(int a, int b) {
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

*유클리드 호제법으로 최대공약수를 구한 뒤, 최소공배수 계산

 

2 13241 최소공배수 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        long a = Long.parseLong(split[0]);
        long b = Long.parseLong(split[1]);
        System.out.println(a * b / gcd(a,b));
    }

    public static long gcd(long a, long b) {
        while (b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

3 1735 분수 합 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numer1 = sc.nextInt();
        int denom1 = sc.nextInt();
        int numer2 = sc.nextInt();
        int denom2 = sc.nextInt();

        int denom = denom1 * denom2;
        int numer = numer1 * denom2 + numer2 * denom1;
        int gcd = gcd(denom, numer);
        System.out.println(numer / gcd + " " + denom / gcd);

    }

    public static int gcd(int a, int b) {
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

*기약 분수 만들기: 분모와 분자의 최대공약수를 구하여 분모, 분자에 나눠줌

 

4 2485 가로수 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[] trees = new int[n];
        for(int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(reader.readLine());
        }

        //가로수 간 거리
        int[] distance = new int[n-1];
        for(int i = 0; i < n - 1; i++) {
            distance[i] = trees[i+1] - trees[i];
        }

        //distance 최대 공약수
        int gcd = distance[0];
        for(int i = 1; i < distance.length; i++) {
            gcd = gcd(gcd, distance[i]);
        }

        //새로 심어야 하는 가로수
        int cnt = 0;
        for(int i = 0; i < distance.length; i++) {
            cnt += distance[i] / gcd - 1;
        }
        System.out.println(cnt);
    }

    public static int gcd(int a, int b) {
        if(b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

 

5 4134 다음 소수 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            long num = Long.parseLong(reader.readLine());
            for(long j = num; j < Long.MAX_VALUE; j++) {
                if(isPrime(j)) {
                    sb.append(j).append("\n");
                    break;
                }
            }
        }
        System.out.print(sb);
    }

    public static boolean isPrime(long num) {
        if(num <= 1) {
            return false;
        }
        for(long i = 2; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

*약수를 찾는 과정에서 √N 까지만 나눠서 소수를 판별하기

 

6 1929 소수 구하기

에라토스테네스의 체

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int M = Integer.parseInt(split[0]);
        int N = Integer.parseInt(split[1]);

        boolean[] prime = new boolean[N - M + 1];
        Arrays.fill(prime, true);

        //1 <= M, N <= 1,000,000
        if(M == 1) {
            prime[0] = false;
        }
        for(int i = 2; i <= Math.sqrt(N); i++) {
            //j는 i의 배수면서 i가 아님 (2*i 부터 시작)
            for(int j = 2 * i; j <= N; j += i) {
                //j가 M과 N 범위 안에 수이고 소수 판별 true 인 경우
                if(M <= j && prime[j-M]) {
                    prime[j-M] = false;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < prime.length; i++) {
            if(prime[i]) {
                sb.append(i+M).append("\n");
            }
        }
        System.out.println(sb);
    }
}

 

7 4948 베르트랑 공준 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //1 ≤ n ≤ 123,456
        boolean[] prime = generatePrime(2 * 123456);

        StringBuilder sb = new StringBuilder();
        while(true) {
            String str = reader.readLine();
            if(str.equals("0")) {
                break;
            }
            int n = Integer.parseInt(str);

            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 boolean[] generatePrime(int max) {
        boolean[] prime = new boolean[max + 1];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for(int i = 2; i <= Math.sqrt(max); i++) {
            if(!prime[i]) {
                continue;
            }
            for(int j = 2 * i; j <= max; j += i) {
                prime[j] = false;
            }
        }
        return prime;
    }
}

 

8 17103 골드바흐 파티션

짝수 N = 두 소수의 합

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        boolean[] prime = generatePrime(1000000);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(reader.readLine());
            int cnt = 0;
            for (int j = 2; j <= N / 2; j++) {
                //j + (N-j) = N
                if (prime[j] && prime[N-j]) {
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.print(sb);
    }

    public static boolean[] generatePrime(int n) {
        boolean[] prime = new boolean[n+1];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(!prime[i]) {
                continue;
            }
            for(int j = 2 * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
        return prime;
    }
}

 

9 13909 창문 닫기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int open = 0;
        //여닫는 횟수가 홀수이면 열린 상태 = 약수가 홀수 개
        //제곱수의 약수는 홀수 개, 제곱수가 아니면 짝수 개
        for(int i = 1; i * i <= n; i++) {
            open++;
        }
        System.out.print(open);
    }
}

 

 

'CT' 카테고리의 다른 글

[BOJ] 17단계 심화2  (0) 2023.04.13
[BOJ] 16단계 조합론  (0) 2023.04.11
[BOJ] 13단계 정렬  (0) 2023.04.06
[BOJ] 12단계 브루트 포스  (0) 2023.04.05
[BOJ] 11단계 시간 복잡도  (0) 2023.04.05

'CT' Related Articles

티스토리툴바