[JAVA] 백준 9단계 약수, 배수와 소수

5086 배수와 약수

나의 답) 100ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (a == 0 && b == 0) {
                break;
            } else if (b % a == 0) {
                sb.append("factor").append("\n");
            } else if (a % b == 0) {
                sb.append("multiple").append("\n");
            } else {
                sb.append("neither").append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}
// 0 0이 입력되면 종료하는 반복문
// 숫자 두 개씩 입력받음
// if) 첫 번째 숫자가 두 번째 숫자의 약수 -> factor
// else if) 첫 번째 숫자가 두 번째 숫자의 배수 -> multiple
// else) -> neither

 

Q) StringBuilder()에 String을 담아 출력할 때 .toString()을 사용하는 것이 좋은지? 아니면 사용하지 않아도 상관없는지?

A)

=> StringBuilder에 담긴 문자열을 출력할 때 .toString()을 사용하는 것이 필수적이지 않지만, 권장된다.

이유)

: StringBuilder는 문자열을 효율적으로 처리하기 위한 클래스이다. 문자열을 연결할 때는 StringBuilder를 사용하면 더 효율적이다. 그러나 StringBuilder 자체는 String 타입이 아니기 때문에, 이를 System.out.print()나 System.out.println()에 출력하려면 String 타입으로 변환해야 한다.

 

다른 사람의 답1) 104ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (a == 0 && b == 0) break;
            if (a > b && a % b == 0) {
                sb.append("multiple").append("\n");
            } else if (a < b && b % a == 0) {
                sb.append("factor").append("\n");
            } else {
                sb.append("neither").append("\n");
            }
        }
        System.out.print(sb.toString());
    }
}

 

다른 사람의 답2) 100ms

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            String[] arr = br.readLine().split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            
            if (a == 0 && b == 0 ) break;
            if ((double) (a % b) == 0.0) {
                sb.append("multiple");
            } else if ((double) (b % a) == 0.0) {
                sb.append("factor");
            } else {
                sb.append("neither");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

2501 약수 구하기

나의 답1) 104ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int count = 0, res = 0;
        
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
               count++;
               if (count == k) {
                   res = i;
                   break;
               }
            }
        }
        
        if (res == 0) System.out.print(0);
        else System.out.print(res);
    }
}
// 한 줄에 N과 K 입력받기
// N의 약수의 개수 구하기
// if) N의 약수의 개수 < K -> 0 출력
// else) N의 약수들 중 K번째로 작은 수 출력

 

나의 답2) 104ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int count = 0, res = 0;
        
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
               count++;
               if (count == k) {
                   res = i;
                   break;
               }
            }
        }
        
        System.out.print(res == 0 ? 0 : res);
    }
}

 

다른 사람의 답) 104ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        ArrayList<Integer> arr = new ArrayList<>();
        
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                arr.add(i);
            }
        }
        
        System.out.print(k <= arr.size() ? arr.get(k - 1) : 0);
    }
}

---

9506 약수들의 합

나의 답1) 112ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = 0;
        
        while (n != -1) {
            n = Integer.parseInt(br.readLine());
            
            if (n == -1) break;
            
            int measure = 0;
            ArrayList<Integer> arr = new ArrayList<>();
            
            for (int i = 1; i < n; i++) {
                if (n % i == 0) {
                    measure += i;
                    arr.add(i);
                }
            }
            
            if (measure == n) {
                sb.append(n).append(" = ");
                for (int i = 0; i < arr.size(); i++) {
                    sb.append(arr.get(i));
                    if (i != arr.size() - 1) {
                        sb.append(" + ");
                    }
                }
                sb.append("\n");
            } else {
                sb.append(n).append(" is NOT perfect.").append("\n");
            }
        }
        System.out.print(sb);
    }
}
// n이 완전수인지 아닌지 판단하는 프로그램
// -1이 입력되기 전까지 n 입력받음
// if) n이 완전수라면 n을 n이 아닌 약수들의 합으로 출력(약수들은 오름차순 나열)
// else) n is NOT perfect. 출력

 

나의 답2) 104ms 다시 보기!!

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        while (true) {
            int n = Integer.parseInt(br.readLine());
            
            if (n == -1) break;  // -1 입력 시 종료
            
            ArrayList<Integer> divisors = new ArrayList<>();
            int sum = 0;
            
            // 1부터 sqrt(n)까지 반복하면서 약수 찾기
            for (int i = 1; i * i <= n; i++) {
                if (n % i == 0) {
                    divisors.add(i);
                    if (i != n / i) {  // 중복된 약수는 추가하지 않음
                        divisors.add(n / i);
                    }
                }
            }
            
            // 약수를 오름차순으로 정렬
            Collections.sort(divisors);
            divisors.remove(divisors.size() - 1);  // 자기 자신을 제외한 약수만 저장

            for (int divisor : divisors) {
                sum += divisor;
            }
            
            if (sum == n) {
                sb.append(n).append(" = ");
                for (int i = 0; i < divisors.size(); i++) {
                    sb.append(divisors.get(i));
                    if (i != divisors.size() - 1) {
                        sb.append(" + ");
                    }
                }
                sb.append("\n");
            } else {
                sb.append(n).append(" is NOT perfect.").append("\n");
            }
        }

        System.out.print(sb);
    }
}

 

sqrt(n)까지만 반복하는 이유

- 약수는 쌍으로 등장한다. 예를 들어, n = 36일 때, 약수 1은 36과 쌍을 이루고, 2는 18과, 3은 12와, 4는 9와 쌍을 이룬다.

- 따라서 약수 중 sqrt(n)보다 큰 값은 이미 sqrt(n)보다 작은 값과 짝을 이루어서 나오므로 따로 다시 계산할 필요가 없다.

---

1978 소수 찾기

나의 답) 108ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(st.nextToken());
            if (isPrime(temp)) count++;
        }
        System.out.print(count);
    }
    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

---

2581 소수

나의 답1) 104ms

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int sum = 0, min = -1;
        
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        
        for (int i = m; i <= n; i++) {
            if (isPrime(i)) {
                sum += i;
                if (min > i || min == -1) {
                    min = i;
                }
            }
        }
        
        if (sum == 0) {
            sb.append(min);
        } else {
            sb.append(sum).append("\n").append(min);
        }
        System.out.print(sb);
    }
    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        for (int i = 2; i *i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

[전체 알고리즘]

1. M 입력받기
2. N 입력받기
3. 소수의 합 출력
4. 소수 중 최솟값 출력(단, 소수가 없을 경우에는 -1만 출력)

 

나의 답2) 100ms

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        
        boolean[] isNotPrime = new boolean[n + 1];
        isNotPrime[0] = isNotPrime[1] = true;
        
        for (int i = 2; i * i <= n; i++) {
            if (!isNotPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }
        
        int sum = 0;
        int min = -1;
        
        for (int i = m; i <= n; i++) {
            if (!isNotPrime[i]) {
                sum += i;
                if (min == -1) {
                    min = i;
                }
            }
        }
        
        if (sum == 0) {
            sb.append(-1);
        } else {
            sb.append(sum).append("\n").append(min);
        }
        System.out.print(sb);
    }
}

 

=> 에라토스테네스의 체 알고리즘 이용

방법)

1. 모든 소수를 한 번에 구하기

2. 소수 범위 필터링

 

m부터만 소수 여부를 확인하면 되는데, 2부터 소수인지 여부를 판별하는 이유)

에라토스테네스의 체는 2부터 시작해 모든 소수를 한 번에 구하는 방법이다.

소수의 배수를 제외해나가는 방식이므로, 특정 범위만을 효율적으로 처리하려면 전체 범위 0부터 n까지를 먼저 처리해야 한다.

 

다른 사람의 답) 104ms

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int sum = 0;
        int min = -1;

        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        
        for (int i = m; i <= n; i++) {
            if (i < 2) continue;
            
            boolean isPrime = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            
            if (isPrime) {
                sum += i;
                if (min == -1) min = i;
            }
        }
        if (min != -1) {
            sb.append(sum).append("\n").append(min);
        } else {
            sb.append(min);
        }
        System.out.print(sb);
    }
}

---

11653 소인수분해

나의 답) 108ms

import java.io.*;
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());
        
        if (n == 1) {
            System.out.print(sb);
            return;
        }
        for (int i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                sb.append(i).append("\n");
                n /= i;
            }
        }
        // 나머지 n이 1보다 크면 소수로 출력
        if (n > 1) {
            sb.append(n).append("\n");
        }
        
        System.out.print(sb);
    }
}