[단계별로 풀어보기-Java] 9단계 약수, 배수와 소수 (에라토스테네스의 체 사용)

백준 사이트 로고

 

안녕하세요~

오늘은 9단계 약수, 배수와 소수 문제를 풀어보겠습니다.

---

✏️ 문제 번호 : 5086
배수와 약수

 

문제 살펴보기

1. 입력 값

10,000이 넘지 않는 두 자연수
마지막 줄에는 0이 2개로 주어짐.
0이 2개일 경우 입력 종료

2. 출력 값

첫 번째 숫자가 두 번째 숫자의 약수라면 factor
배수라면 multiple
둘 다 아니라면 neither

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

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

        while (true) {
            String input = br.readLine();
            if (input == null || input.isEmpty()) break; // 입력이 없으면 종료

            String[] numbers = input.split(" ");
            int a = Integer.parseInt(numbers[0]);
            int b = Integer.parseInt(numbers[1]);

            if (a == 0 && b == 0) break; // 입력이 "0 0"이면 종료

            if (b % a == 0) {
                sb.append("factor\n"); // a가 b의 약수
            } else if (a % b == 0) {
                sb.append("multiple\n"); // a가 b의 배수
            } else {
                sb.append("neither\n"); // 둘 다 아님
            }
        }

        System.out.print(sb.toString());
    }
}

 

풀이 과정

입력값이 null일 수도 있으므로

if(input == null || input.isEmpty()) break;

추가하여 입력이 종료될 경우 탈출하게 합니다.

그 후, 두 숫자 a와 b에 대해 조건을 체크합니다.

b % a == 0 이면, 
a는 b의 약수 -> factor

a % b == 0 이면,
a는 b의 배수 -> multiple

위 두 조건이 아니면,
neither

 

---

✏️ 문제 번호 : 2501
약수 구하기

 

문제 살펴보기

1. 입력 값

첫째 줄에 N과 K를 입력
K는 1이상 N이하이다.

2. 출력 값

N의 약수들 중 K번째로 작은 수를 출력

만약, N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하기 않을 경우에는 0을 출력

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));

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

        int cnt = 0;

        for (int i = 1; i <= N; i++) {
            if (N % i == 0) {
                cnt++;
                if (cnt == K) {
                    System.out.println(i);
                    return;
                }
            }
        }

        System.out.println(0);
    }
}

 

풀이 과정

BufferedReader와 StringTokenizer를 사용해
N, K 입력 받기

for문을 돌면서 1부터 N까지 순회합니다.

N % i == 0 이면, i는 N의 약수
약수는 cnt로 셉니다.

k번째 약수를 찾으면 출력하고 종료합니다.

만약 없다면 0을 출력합니다.

 

---

✏️ 문제 번호 : 9506
약수들의 합

 

문제 살펴보기

1. 약수 구하기
n의 모든 약수를 찾아서 리스트에 저장

2. 약수의 합 계산
n 자신을 제외한 약수들의 합을 계산

3. 완전 수 판별
n이 완전수라면,
n = 약수1 + 약수2 + ... 형태로 출력

4. 입력 처리
여러 개의 입력을 처리해야 하며, -1이 입력되면 종료

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

public 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().trim());
            if (n == -1) break;

            int[] div = new int[n / 2]; // 최대 n/2개의 약수를 저장할 배열
            int count = 0; // 현재 약수 개수
            int sum = 0; // 약수의 합

            // 약수 찾기
            for (int i = 1; i <= n / 2; i++) {
                if (n % i == 0) {
                    div[count++] = i;
                    sum += i;
                }
            }

            // 완전수 판별
            if (sum == n) {
                sb.append(n).append(" = ");
                for (int i = 0; i < count; i++) {
                    sb.append(div[i]);
                    if (i < count - 1) {
                        sb.append(" + ");
                    }
                }
                sb.append("\n");
            } else {
                sb.append(n).append(" is NOT perfect.\n");
            }
        }
        
        System.out.print(sb.toString());
    }
}

 

풀이 과정

1. BufferedReader와 StringBuilder를 사용해서 성능 개선했습니다.

2. while문을 사용해 -1이 입력될 때까지 반복적으로 입력 받았고
입력을 문자열로 받아 trim()으로 공백 제거했습니다.

3. 약수를 저장할 배열 생성
div = new int[n/2];
n의 약수는 최대 n/2개 까지 존재하므로 배열을 생성합니다.

4. 반복문을 통해 약수 찾기
i =1부터 n/2까지 반복하면서 n%i==0이면 약수로 판단
div[count++] = i 방식으로 배열에 저장해 count를 증가합니다.
sum += i는 약수들의 합을 계산합니다.

5. 완전수 판별
완전수 확인을 위해 자신을 제외한 약수의 합(sum)이 n과 같으면 완전수입니다.

n = 약수1 + 약수2 + ... 형태로 출력
for 문을 사용해 약수 리스트를 하나씩 StringBuilder에 추가합니다.
마지막 약수 뒤에는 " + "를 추가하지 않도록 조건 처리합니다. (if (i < count - 1))

완전수가 아니면 "n is NOT perfect."를 출력합니다.

 

---

✏️ 문제 번호 : 1978
소수 찾기

(에라토스테네스의 체 적용)

 

문제 살펴보기

주어진 수 N개 입력
입력한 N개 중 소수가 몇 개인지 출력하기

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

public class Main {
    private static final int MAX = 1000; // 자연수의 최대 범위
    private static boolean[] isPrime = new boolean[MAX + 1]; // 소수 여부 저장 배열

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

        sieve();

        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 소수 개수 카운트
        int cnt = 0;
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            if (isPrime[num]) {
                cnt++;
            }
        }

        System.out.print(cnt);
    }

// 에라토스테네스의 체를 이용 (1~1000까지 소수 판별)
    private static void sieve() {
        for (int i = 2; i <= MAX; i++) {
            isPrime[i] = true; // 초기값을 모두 소수(true)로 설정
        }

        for (int i = 2; i * i <= MAX; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= MAX; j += i) {
                    isPrime[j] = false; // 배수는 소수가 아님
                }
            }
        }
    }
}

 

풀이 과정

1. 에라토스테네스의 체 사용 (sieve 배열)
1~1000 범위의 수에 대해 미리 소수를 판별하여 배열에 저장
이를 이용하면 소수 판별을 O(1)로 빠르게 수행할 수 있습니다.

 

에라토스테네스의 체

소수를 빠르게 판별하는 알고리즘
1부터 N까지의 한 번에 많은 소수를 구할 때 가장 효율적인 방법 중 하나로,
시간 복잡도가 O(N log log N)으로 매우 빠른 편입니다.

원리
- 2부터 시작해서 남아있는 가장 작은 수를 소수로 판별
- 그 소수의 배수를 전부 제거
- 다음으로 남아있는 가장 작은 수를 소수로 판별하고 다시 배수를 제거
- 이 과정을 N까지 반복하면, 소수만 남음

private static void sieve() {
    for (int i = 2; i <= MAX; i++) {
        isPrime[i] = true; // 2부터 시작해서 모든 수를 소수로 가정
    }

    for (int i = 2; i * i <= MAX; i++) {
        if (isPrime[i]) { // i가 소수라면
            for (int j = i * i; j <= MAX; j += i) {
                isPrime[j] = false; // i의 배수들은 소수가 아님
            }
        }
    }
}

isPrime[i] = true로 초기화 → 모든 수를 소수로 가정하고
2부터 √MAX까지 검사하면서 배수들을 모두 소수가 아니라고 표시합니다.

O(N log log N)의 시간 복잡도로 빠르게 소수를 판별합니다.

 

2. BufferedReader, StringTokenizer를 활용해 숫자들을 하나씩 가져와 빠른 입력 받음

3. while문에 hasMoreTokens() 메서드 사용
hasMoreToken() 메서드를 사용해 남아있는 토큰이 있는 동안 반복합니다.

3. sieve 배열을 이용해 소수 개수 계산
isPreime[num]이 true이면 소수로 간주하고 cnt를 증가

 

---

✏️ 문제 번호 : 2581
소수

(에라토스테네스의 체 적용)

 

문제 살펴보기

1. 입력값
입력의 첫째 줄이 M, 둘째 줄이 N
M과 N은 10,000이하의 자연수
M은 N보다 작거나 같다.

2. 출력값
M이상 N이하의 자연수 중, 소수인 것을 모두 찾아 첫째줄에 합
둘째 줄에 그 중 최솟값 출력

단, M이상 N이하의 자연수 중 소수가 없을 경우에는 -1을 출력

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

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

        // 1. 에라토스테네스의 체를 사용하여 N까지의 모든 소수를 판별
        boolean[] isPrime = sieve(N);

        int sum = 0;
        int minPrime = Integer.MAX_VALUE;

        // 2. M 이상 N 이하의 소수 찾기
        for (int num = M; num <= N; num++) {
            if (isPrime[num]) { // 소수라면
                sum += num; // 합 계산
                minPrime = Math.min(minPrime, num); // 최솟값 갱신
            }
        }

        // 3. 결과 출력
        if (sum == 0) {
            System.out.println("-1"); // 소수가 하나도 없으면 -1 출력
        } else {
            System.out.println(sum);  // 소수의 합 출력
            System.out.println(minPrime); // 최솟값 출력
        }
    }

    // 에라토스테네스의 체: N까지의 모든 소수 판별
    private static boolean[] sieve(int N) {
        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true); // 모든 수를 소수로 가정
        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) { // i가 소수이면
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false; // i의 배수들은 소수가 아님
                }
            }
        }
        return isPrime;
    }
}

 

풀이 과정

1. BufferedReader를 사용해 빠르게 입력 받음

2. 에라토스테네스의 체를 사용해 소수 판별 (sieve 함수)
sieve(N) 함수를 호출하여 1 ~ N까지의 소수 여부를 저장하는 배열 (isPrime[])을 생성합니다.
isPrime[i] = true이면 i는 소수, false이면 i는 소수가 아닙니다.

3. M이상 N이하의 소수 찾기 (소수 합과 최솟값 구하기)
소수들의 합을 저장하고 소수 중 최솟값을 저장해서 Integer.MAX_VALUE로 초기화합니다.
M~N 범위를 순회하면서 소수를 찾고 합산합니다.
첫 번째 소수를 찾으면 minPrime을 해당 소수로 설정합니다.

4. 소수가 하나도 없으면 -1 출력, 소수가 있다면 합(sum), 최솟값(minPrime)출력

 

5. 에라토스테네스의 체 (sieve(N))

private static boolean[] sieve(int N) {
    boolean[] isPrime = new boolean[N + 1];
    Arrays.fill(isPrime, true); // 모든 수를 소수(true)로 가정
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) { // i가 소수이면
            for (int j = i * i; j <= N; j += i) {
                isPrime[j] = false; // i의 배수들은 소수가 아님
            }
        }
    }
    return isPrime;
}

(1) 1부터 N까지 모든 수를 소수(true)라고 가정 (Arrays.fill(isPrime, true))
(2) 0과 1은 소수가 아니므로 false 설정
(3) 2부터 시작하여 배수를 제거
i가 소수라면, i의 배수들을 전부 false로 설정 (소수가 아님)
i * i부터 N까지 i의 배수를 false 처리

(4) 최종적으로 isPrime[i] = true이면 i는 소수

만약, N=10일 때

숫자	초기값	2 처리	3 처리	5 처리	최종 결과
0	❌	❌	❌	❌	❌
1	❌	❌	❌	❌	❌
2	✅	✅	✅	✅	✅
3	✅	✅	✅	✅	✅
4	✅	❌	❌	❌	❌
5	✅	✅	✅	✅	✅
6	✅	❌	❌	❌	❌
7	✅	✅	✅	✅	✅
8	✅	❌	❌	❌	❌
9	✅	✅	❌	❌	❌
10	✅	❌	❌	❌	❌

✅결과: {2, 3, 5, 7}이 소수입니다.

 

---

✏️ 문제 번호 : 11653
소인수분해

 

import java.io.*;

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().trim());

        if (N == 1) return;

        while (N % 2 == 0) {
            System.out.println(2);
            N /= 2;
        }

        for (int i = 3; i * i <= N; i += 2) {
            while (N % i == 0) {
                System.out.println(i);
                N /= i;
            }
        }

        if (N > 1) {
            System.out.println(N);
        }
    }
}

 

풀이 과정

1. 짝수(2)와 홀수 나누기 구분
while(N%2==0) 반복문으로 2로 나눌 수 있을 때 모두 나눠줍니다.

2. 제곱근까지 검사, 홀수 검사
for(int i=3; i*i <=N; i+=2)문에서 i*i<=N까지만 검사하여 불필요한 연산을 줄입니다.
i+=2로 홀수를 검사합니다.

3. 마지막으로 남은 값이 1보다 크면 출력
모든 나눗셈이 끝난 후 N>1이면 그 자체가 소수이므로 출력합니다.

 

---

이처럼 에라토스테네스의 체를 활용하여
백준 9단계 문제를 풀어봤습니다.

저는 다음 백준 10단계 기하:직사각형과 삼각형의 문제 풀이로 돌아오겠습니다 ~

 

오코완
(오늘도 코테 공부 완료)

인스타그램 : pettydust