[백준] 약수, 배수와 소수2_3

서론

---

약수, 배수와 소수2

6~9 문제풀이

---

4948 : 베르트랑 공준

---

문제

---

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

해설

---

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

public 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) {
            int N = Integer.parseInt(br.readLine());
            int cnt = 0;
            if(N == 0){
                break;
            }
            for (int i = N+1; i <= 2*N; i++) {
                boolean check = true;
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if(i % j == 0){
                        check = false;
                        break;
                    }
                }
                if(check){
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

이전 문제인 (1929 : 소수구하기) 와 동일한 방법을 사용하였지만,

n < prime <= 2n 사이의 소수의 개수를 새도록 코드를 작성하였다.

---

17103 : 골드바흐 파티션

---

문제

---

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

---

해설

---

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

public 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));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N[] = new int[T];
        int max = -1;

        for (int i = 0; i < T; i++) {
            N[i] = Integer.parseInt(br.readLine());
            //입력받은 수 중 가장 큰 값을 설정
            max = N[i] > max ? N[i] : max;
        }

        boolean primes[] = eratosthenes(max); //0 ~ 가장 큰 수까지 소수를 판별한다. 
        for (int i = 0; i < T; i++) {
            int cnt = 0;
            //N[i]/2까지 (순서만 바뀐 것은 같은 파티션이므로)
            for (int j = 2; j <= N[i]/2; j++) {
            	//j + N[i] - j = N[i] 이므로 두 수가 모두 소수라면 cnt++
                if(!primes[j] && !primes[N[i]-j]){
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static boolean[] eratosthenes(int n) {
        boolean primes[] = new boolean[n+1];
        primes[0] = primes[1] = true;

        for (int i = 2; i * i <= n; i++) {
            if(!primes[i]){
                for (int j = i * i; j <= n; j += i) { //j += i
                    primes[j] = true;
                }
            }
        }
        return primes;
    }
}

먼저 해당 문제는 에라토스테네스의 체 알고리즘을 사용하였다.

(처음 알게된 알고리즘이라, 에라토스테네스의 체 알고리즘은 인터넷을 참고하였다.)

에라토스테네스의 체는 다음에 자세히 알아보도록 하겠다.

---

13909 : 창문 닫기

---

문제

---

https://www.acmicpc.net/problem/13909

13909번: 창문 닫기

---

해설

---

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

public 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));
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;
        for (int i = 1; i * i <= N; i++) {
            cnt++;
        }
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
    }
}

이 문제는 케이스를 나누어 생각해야 풀 수 있는 문제였다.

마지막에 열려있는 경우와 닫혀있는 경우 2가지로 나누어보면 아래와 같다.

	약수의 개수
열림	홀수
닫힘	짝수

여기서 약수의 개수가 홀수인 경우는 바로 제곱수를 의미한다.

(N = 25이면 약수 = {1,5,25}, N = 24이면 약수 = {1,2,3,4,6,8,12,24}를 보면,

제곱수가 아니면 두 약수의 곱으로 해당 수를 만들어낼 수 있다.)

따라서, 제곱수가 N보다 작으면 카운팅해주고 이를 출력한다.

---

결론

---

 

몰랐던 것을 알게 되어 유익했고, 세상에는 고수들이 많다는 것을 다시 한번 느낄 수 있었다!.

---