백준 17103번[c언어] : 골드바흐 파티션

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

17103번: 골드바흐 파티션

---

2022.03.21 - [백준] - 백준 9020번 [c언어] : 골드바흐의 추측

백준 9020번 [c언어] : 골드바흐의 추측

9020번 골드바흐의 추측과 매우 비슷한 문제이다.

 

풀이

• 에라토스테네스의 체로 배열에 소수가 아닌 값은 0을 저장하고 소수인 값은 소수값을 저장한다.
• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

• 배열의 0과 1은 소수가아니므로 반복문은 2부터 시작한다
• 문제에서 순서가 다른 것은 개수로 치지 않는다고 햇으니 우리는 합이되는 모든 경우의 수를 구하고 /2를 해주면 된다.(순서가 다른것들은 제거해야하므로)
• 10같은 경우 5+5 같은수로 10을 만들 수 있으므로 a-i==i인경우는 경우의수를 하나 더 추가해준다.

#include<stdio.h>

int main() {
	//에라토스테네스의 체
	int arr[1000001] ;
	for (int i = 2; i < 1000001; i++)
		arr[i] = i;   //배열[i]에 자기자신 i를 넣는다

	for (int i = 2; i <= 1000001; i++)
		for (int j = 2; j * i <= 1000001; j++)
			arr[i * j] = 0; 
            //에라토스테네스의 체로 소수가 아닌 숫자들은 0을 넣는다.

	int ntest;
	scanf("%d", &ntest);
	for (int i = 0; i < ntest; i++) {
		int a;
		int answer = 0;
		scanf("%d", &a);
		for (int i = 2; i < a; i++) {
			if (arr[a - i] + arr[i] == a) {
				answer++;
				if (a - i == i) //10에서 5+5인경우
					answer++;
			}
			
		}
		printf("%d\n", answer / 2);
	}
}