[백준 - 17014][SILVER 1][해설 X] - Pretty Average Primes (JAVA)

문제 링크

---

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

 

문제

---

For various given positive integers N > 3, find two primes, A and B such that N is the average (mean) of A and B. That is, N should be equal to (A+B)/2.

Recall that a prime number is an integer P > 1 which is only divisible by 1 and P. For example, 2, 3, 5, 7, 11 are the first few primes, and 4, 6, 8, 9 are not prime numbers.

 

입력

---

The first line of input is the number T (1 ≤ T ≤ 1000), which is the number of test cases. Each of the next T lines contain one integer Ni (4 ≤ Ni ≤ 1000000, 1 ≤ i ≤ T).

For 6 of the available 15 marks, all Ni < 1000.

 

출력

---

The output will consist of T lines. The ith line of output will contain two integers, Ai and Bi, separated by one space. It should be the case that Ni = (Ai + Bi)/2 and that Ai and Bi are prime numbers.

If there are more than one possible Ai and bi for a particular Ni, output any such pair. The order of the pair Ai and Bi does not matter.

It will be the case that there will always be at least one set of values Ai and Bi for any given Ni.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static final int MAX_N = 2_000_000;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] isNotPrime = new boolean[MAX_N+1];
        List<Integer> primeList = new ArrayList<>();
        
        //에라토스테네스의 체로 소수 판정 및 소수 리스트 생성
        for(int i=2;i<isNotPrime.length;i++){
            if(isNotPrime[i]){
                continue;
            }
            primeList.add(i);

            for(int j=i*2;j<isNotPrime.length;j+=i){
                isNotPrime[j] = true;
            }
        }

        int T = Integer.parseInt(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //모든 테스트 케이스를 받아 A와 B 탐색
        for(int testcase=1;testcase<=T;testcase++){
            int N = Integer.parseInt(br.readLine());

            //A와 B가 모두 소수이고 (A*B)/2 = N을 만족하는지 판정
            for(int i=0;primeList.get(i) <= N;i++){
                int A = primeList.get(i);
                int B = N*2 - primeList.get(i);
                
                //B가 소수이면 주어진 조건을 만족하므로 출력
                if(!isNotPrime[B]){
                    bw.write(A+" "+B);
                    bw.newLine();
                    break;
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

실행 결과

---

 

팁

---

• 소수 판정은 에라토스테네스의 체가 좋다.