728x90
https://www.acmicpc.net/problem/15711
에라토스테네스의 체를 사용하여 풀 수 있다!
2를 제외한 모든 홀수가 소수이다.
1) 두 수의 합이 4보다 작으면 무조건 소수 2개로 나누지 못함!
2) 두 수의 합이 짝수이면 모두 가능
3) 두 수의 합이 홀수이면
두 수의 합의 값 4 * 1012 의 루트값 2000000까지의 소수값을 확인하여 판단한다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static boolean[] isPrime = new boolean[2000001];
public static List<Integer> list = new ArrayList<>();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
eratosthenes();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
String result = "NO";
long sum = a + b;
if (sum < 4) {
sb.append("NO").append("\n");
} else if (sum % 2 == 0) {
sb.append("YES").append("\n");
} else {
if (check(sum - 2)) {
sb.append("NO").append("\n");
} else {
sb.append("YES").append("\n");
}
}
}
System.out.println(sb);
}
static boolean check(long num) {
if(num<=2000000) return isPrime[(int)num];
for(int i=0;i<list.size();i++) {
if(num%list.get(i)==0) {
return true;
}
}
return false;
}
static void eratosthenes() {
isPrime[0]= isPrime[1]=true;
for(int i=2;i<=2000000;i++) {
if(!isPrime[i]) {
list.add(i);
for(int j=i*2;j<=2000000;j+=i) {
isPrime[j]=true;
}
}
}
}
}
'Java' 카테고리의 다른 글
[백준 1826] 연료 채우기 (JAVA) (0) | 2023.03.28 |
---|---|
[백준 6588] 골드바흐의 추측 (JAVA) (0) | 2023.03.25 |
[백준 2485] 가로수 (JAVA) (0) | 2023.03.23 |
[백준 2206] 벽 부수고 이동하기 (JAVA) (0) | 2023.03.23 |
[백준 2583] 영역 구하기 (JAVA) (0) | 2023.03.23 |