17103번 골드바흐 파티션 with C++

문제

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

17103번: 골드바흐 파티션

 

해결한 방법

1. 소수 리스트를 만든다. (소수 구하기 문제 참고 https://everydaystudy.tistory.com/52)
2. 골드바흐의 추측을 만족시키는 소수 조합을 찾을때마다 count 1을 더해준다
3. 입력받은 모든 수에 2번과정을 거치고 count를 출력해줍니다.

#include <iostream>
#include <cmath>
#define MAX 1000001
using namespace std;

int input_li[100001];
bool prime[MAX];
int prime_li[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n;

	int max = 0;
	for (int i = 0; i < n; i++) {
		cin >> input_li[i];
		if (max < input_li[i])
			max = input_li[i];
	}

	fill_n(prime, MAX, 1);
	prime[0] = false;
	prime[1] = false;

	for (int i = 2; i < sqrt(max); i++) {
		if (prime[i]) {
			for (int j = i * 2; j <= max; j += i) {
				prime[j] = false;
			}
		}
	}

	int prime_count = 0;
	for (int i = 0; i <= max; i++) {
		if (prime[i]) {
			prime_li[prime_count] = i;
			prime_count++;
		}
	}

	int count;
	for (int i = 0; i < n; i++) {
		count = 0;
		for (int j = 0; prime_li[j] <= input_li[i] / 2; j++) {
			if (prime[input_li[i] - prime_li[j]]) {
				count++;
			}
		}
		cout << count << "\n";
	}

	return 0;
}