2021-11-19

기본 수학2
소수와 기하를 다뤄 봅시다.

5단계 4948 베르트랑 공준

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

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[246913];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      get_prime();
      
      while(true) {
         int n;
         n = sc.nextInt();
         
         if(n == 0) break;
         
         int count = 0;
         
         for(int i=n+1; i<=2*n; i++) {
            if(!prime[i])
               count++;
         }
         System.out.println(count);         
      }
   }

   private static void get_prime() {
      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;
         }
      }
   }
}

2단계 2581 소수

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

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

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

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

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int M;
      M = sc.nextInt();
      int N;
      N = sc.nextInt();
      int sum = 0;
      int min = N;
      int tmp = 0;
      
      for(int i=M; i<=N; i++) {
         tmp = 0;
         for(int j=1; j<=i; j++) {
            if(i%j == 0)
               tmp++;
               }
            if(tmp == 2) {
               sum += i;
               if(min>i)
                  min = i;
               }
            }
      
            if(sum == 0) {
               System.out.println(-1);
            } else {
               System.out.println(sum);
               System.out.println(min);
            }
   }
}

6단계 9020 골드바흐의 추측

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

문제

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[10001];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      get_prime();
      
      int T;
      T = sc.nextInt();
      
      while(T-- > 0) {
         int n;
         n = sc.nextInt();
         int first_partition = n/2;
         int second_partition = n/2;
         
         while(true) {
            if(!prime[first_partition] && !prime[second_partition]) {
               System.out.println(first_partition + " " + second_partition);
               break;
            }
            first_partition--;
            second_partition++;
         }
      }
   }
      
   private static void get_prime() {
      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;
         }
      }
   }
}

7단계 1085 직사각형에서 탈출

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

문제

한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 x, y, w, h가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[10001];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int x;
      x = sc.nextInt();
      int y;
      y = sc.nextInt();
      int w;
      w = sc.nextInt();
      int h;
      h = sc.nextInt();
      
      int x_min = Math.min(x, w-x);
      int y_min = Math.min(y, h-y);
      
      System.out.println(Math.min(x_min, y_min));
   }
}

8단계 3009 네 번째 점

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

문제

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

입력

세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

직사각형의 네 번째 점의 좌표를 출력한다.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int[] coord_1 = { sc.nextInt(), sc. nextInt() } ;
      int[] coord_2 = { sc.nextInt(), sc. nextInt() } ;
      int[] coord_3 = { sc.nextInt(), sc. nextInt() } ;
      
      int x;
      int y;
      
      if(coord_1[0] == coord_2[0]) {
         x = coord_3[0];
      } else if( coord_1[0] == coord_3[0]) {
         x = coord_2[0];
      } else {
         x = coord_1[0];
      }
      
      if (coord_1[1] == coord_2[1]) {
         y = coord_3[1];
      } else if (coord_1[1] == coord_3[1]) {
         y = coord_2[1];
      } else {
         y = coord_1[1];
      }
      System.out.println(x + " " + y);
   }
}

9단계 4153 직각삼각형

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

문제

과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.\

입력

입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.

출력

각 입력에 대해 직각 삼각형이 맞다면 "right", 아니라면 "wrong"을 출력한다.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      while(true) {
         int x;
         x = sc.nextInt();
         int y;
         y = sc.nextInt();
         int z;
         z = sc.nextInt();
         
         if(x==0 && y==0 && z==0)
            break;
      
         if((x * x + y * y) == z * z) {
            System.out.println("right");
         } else if(x * x == (y * y + z * z)) {
            System.out.println("right");
         } else if(y * y == (z * z + x * x)) {
            System.out.println("right");
         } else {
            System.out.println("wrong");
         }
      }
   }
}