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

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

9020번: 골드바흐의 추측

 

 

---

○ 에라토스테네스의 체를 이용하여 배열에 소수이면 0을 저장하고 소수가 아닌 값은 1을 저장한다.

 

○ 소수 n을 입력받고 2로 나눈값을 check라고 하자

 

○ 반복문 (check부터 시작해서 check를 --시킴)

 

○ 배열의[check]이 1이 아니라면 그 수는 소수이다 만약 배열의[check]이 소수이고  배열의[n-check]가        소수가 아닐 때 그 두수를 더하면 n과 같아진다

 

 

[첫 번째 시간이 많이걸리는 풀이 :76ms]

배열을 하나하나 돌아가면서 비교해서 시간이 오래걸림

#include<stdio.h>

int main() {
	
	int c[10001] = { 0 };
	c[1] = 1;
	for (int i = 2; i <= 10001; i++)
		for (int j = 2; j * i <= 10001; j++)
			c[i * j] = 1;
	int p;
	int ntest;
	int n;
	int check;
	scanf("%d", &ntest);
	for (int i = 0; i < ntest; i++) {
		scanf("%d", &n);
		check = n / 2;
		if (!c[check]) {
			printf("%d %d\n", check, check);
		}
		else {
			for (int j = check; j <= n; j++) {
				p = 0;
				if (c[j] == 0) {
					for (int k = 2; k <= check; k++) {
						if (c[k] == 0) {
							if (j + k == n) {
								printf("%d %d\n", k, j);
								p = 1;
								break;
							}
						}
					}
				}
				if (p == 1)
					break;
			}
		}
	}
}​

 

 

 

[두번째 인터넷을 참조한 풀이]

#include<stdio.h>

int main() {
	
	int c[10001] = { 0 };
	c[1] = 1;
	for (int i = 2; i <= 10001; i++)
		for (int j = 2; j * i <= 10001; j++)
			c[i * j] = 1;
	
	int ntest;
	int n;
	int check;
	scanf("%d", &ntest);
	for (int i = 0; i < ntest; i++) {
		scanf("%d", &n);
		check = n / 2;
		for (int m = check; m > 0; m--) {
			if (c[m] != 1 && c[n - m] != 1) {
				printf("%d %d\n", m, n - m);
				break;
			}
		}
	}
}