BackJoon Algorithm - Java
문제
- 에라토스테네스 체 알고리즘을 이용하면 쉽게 풀수있다.
- 입력받은 수 /2 에 가장 근접한 수가 가장 차이가 작은수 이므로
prime / 2
부터 돌려본다.
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Back_9020 {
public static void main(String[] args) throws IOException {
// given
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int test_count = Integer.parseInt(br.readLine());
// when
for (int i = 0; i < test_count; i++) {
int num = Integer.parseInt(br.readLine());
boolean prime[] = new boolean[num + 1];
// 0하고 1은 소수가 아니다.
prime[0] = true;
prime[1] = true;
// 에라토스테네스 체
for (int j = 2; j < Math.sqrt(prime.length); j++) {
for (int k = j * j; k < prime.length; k += j) {
prime[k] = true;
}
}
for(int j = prime.length/2; j<= prime.length ; j++){
// 소수일때
if (prime[j] == false){
int prime_count = num - j;
// 뺀수가 소수일때 가장 근접한 수가 차가 가장적다.
if( prime[prime_count] == false){
int first_count = prime_count;
int last_count = j;
sb.append(first_count).append(" ").append(last_count).append("\n");
break;
}
}
}
}
// then
System.out.println(sb);
br.close();
}
}
댓글남기기