백준 9020번:골드바흐의 추측 (에라토스테네스의 체)

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

9020번: 골드바흐의 추측

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

 

이문제의 포인트

1.이번 문제는 에라토스테네스의 체를 알면 쉽게 푸는 문제이다.

 

에라토스테네스의 체란?

1. 2부터 시작해서 n까지 진행한다.
2. 가장 작은 수를 선택한다.
3. 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.

즉 에라토스테네스의 체로 소수인 수를 미리 다 지정하고 갈수 있다. 

장점: 소수를 많이 구해야 할 필요가 있거나 여러번 구해야 할 때 미리 저장해둔 값으로 인해 불필요한 연산수를 줄 일 수 있다. 시간복잡도가 많이 사라진다.

 

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int prime[1000001] = { 0 };
void primesearch() {                                      //에라토스테네스의 체
	for (int i = 2; i <= 1000000; i++)
		prime[i] = i;
	for (int i = 2; i <= 1000000; i++) {             
		if (prime[i] == 0)
			continue;
		for (int j = i + i; j <= 1000000; j = j + i) {            //i의 배수값 지우기
			if (prime[j] == 0)
				continue;
			else 
				prime[j] = 0;
		}
	}
	

}
int main()
{
	int n;
	int max=0, min=0;
	int t;
	cin >> t;
	primesearch();
	while (t--) {
		cin >> n;
		for (int i = 2; i <= n/2; i++) {                         //n/2까지 하는 이유는 이 이상을 넘어가도 똑같은거 반복이기 때문
			if (n == (prime[i] + prime[n - i])) {
				min = prime[i];
				max = prime[n - i];
			}
		}
		cout << min << ' ' << max << '\n';

	}
	
	return 0;
}