main

* 유클리드 호제법 공부하기 * BigInteger 내장함수 gcd, lcm 사용가능 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int[] arr = new int[10000 + 1]; for (int i = 1; i < arr.length; i++) { if (i == 1) { arr[i] = -1; } else { arr[i] = i; } } // 제곱근 범위 나누기 for (int i = 3; i < arr.length; i++) { for (int j = 2; j

* 소수판정 : 제곱근 범위 나누기법 사용 * 두 소수의 차이가 가장 작은 골드바흐 파티션을 찾기 위해서 num/2 부터 1씩 줄여 나가면서 찾음. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int[] arr = new int[10000 + 1]; for (int i = 1; i < arr.length; i++) { if (i == 1) { arr[i] = -1; } else { arr[i] = i; } } // 제곱근 범위 나누기법 for (int i = 3; i < ..

* 소수 판별 * 제곱근 범위 나누기법 사용함. ; 소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); int[] arr = new int[123456 * 2 + 1]; for (int i = 1; i < arr.length; i++) { if (i == 1) { arr[i] = -1; } else { arr[i..

* 소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 * 1, 2 예외 처리 (1은 소수 아님, 2는 소수임) * M, N이 같은 경우 * '에라토스테네스의 체'로 풀었다. (변형하여 O(n)의 시간 복잡도를 이룰 수 있다.) * 제곱근 범위 나누기 법으로도 풀 수 있음. ; 소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Scanner scan = new S..

* 좌표를 저장하기 위해 Class 를 만들어 사용했다. import java.io.*; import java.util.*; public class Main { static int width; static int height; static class Pair { int x, y; Pair(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); width = scan.nextInt(); height = scan.nextInt(); int N = scan.nextInt(); Pair[] arr = new Pai..