PS/BOJ
백준 17103번: 골드바흐 파티션 (C++)
도비(Doby)
2022. 7. 24. 22:51
https://www.acmicpc.net/problem/17103
17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
Solved By: Primality Test
#include <iostream>
#include <cmath>
#include <memory.h>
#define MAX 1000000
using namespace std;
int T;
int n;
bool isPrime[MAX];
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
void getPrime(){
memset(isPrime, true, sizeof(isPrime));
for(int i = 2; i <= sqrt(MAX); i++){
if(isPrime[i]){
for(int j = i + i; j <= MAX; j += i){
isPrime[j] = false;
}
}
}
return;
}
int gold(int v){
//cout << "Value is " << v * 2 << '\n';
int cnt = 0;
for(int i = 2; i <= v; i++){
if(isPrime[i] && isPrime[2 * v - i]){
//cout << i << ' ' << 2 * v - i << '\n';
cnt++;
}
}
return cnt;
}
int main(){
fastIO();
getPrime();
cin >> T;
while(T--){
cin >> n;
cout << gold(n / 2) << '\n';
}
return 0;
}