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

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

9020번: 골드바흐의 추측

---

• 문제

---

• 문제풀이

기본적으로 에라토스테네스의 체를 활용하여 소수를 분리해놓고 입력받은 수 중위수부터 2번째까지 소수를 찾아 입력하면 골드바흐 파티션이 나오게 된다.

 

[알고리즘] 에라토스테네스의 체

---

• 코드 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define _CRT_SECURE_NO_WARNINGS

int a[10001];
int number = 10001;
void Sieve() {

	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}

	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue;

		for (int j = 2 * i; j <= number; j += i) {
			a[j] = 0;
		}
	}
	
	
}
int main(void)
{
	int N;
	int input;
	scanf("%d", &N);
	Sieve();
	
	for (int i = 0; i<N; i++) {
		scanf("%d", &input);
		for (int j = input/2; j >= 2; j--) {
			if (a[j]!=0&&a[input-j]!=0) {
				printf("%d %d\n", j,input-j);
				break;
			}
		}
	}

}

---

• 후기

C언어가 이번엔 더 쉬웠다