(17103) 골드바흐 파티션

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

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 8번째

 

 

 

#include <iostream>
using namespace std;
#define p 1000001

int main() 
{
  bool soe[p]= {true, true, false, };
  
  for(int i=4;i<=p;i+=2)  soe[i]= true;
  for(int i=3;i*i<=p;i+=2){
    if(soe[i])  continue;
    
    for(int j=i;i*j<=p;j+=2)  soe[i*j]= true;
  }
  
  int T;
  
  cin >> T;
  
  while(T--){
    int n, res= 0;
    
    cin >> n;
    
    for(int i=2;2*i<=n;i++){
      if(!soe[i] && !soe[n-i])  res++;
    }
    
    cout << res << "\n";
  }
  
  return 0;
}