백준 17103 골드바흐 파티션(Java)

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

17103번: 골드바흐 파티션

---

 

해석 및 팁

 

---

 

이 문제는 에라토스테네스의 체를 이용해서 풀면 되는 문제입니다. 먼저 1000000까지의 소수를 모두 구해놓은 뒤 범위 내의 소수의 개수를 구하면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();

    boolean[] arr= new boolean[1000001];

    arr[0] = true;
    arr[1] = true;
    for(int i = 2; i * i <= 1000000; i++) {
      if(arr[i] == true) continue;
      for(int j = i * i; j <= 1000000; j += i) arr[j] = true;
    }

    int t = sc.nextInt();
    
    for(int i = 0; i < t; i++) {
      int count = 0;
      int n = sc.nextInt();
      for(int j = 2; j <= n; j++) {
        if(arr[j] == false && arr[n-j] == false) count++;
      }
      if(count % 2 == 1) sb.append(count / 2 + 1).append("\n");
      else sb.append(count / 2).append("\n");
    }

    System.out.println(sb);
  }
}