[C++][수학2/골드바흐의 추측(9020)] 소수

백준 골드바흐의 추측 바로가기

 

 

[소스 코드]

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

bool isPrime(int num) {
	if (num == 1) return false;
	if (num == 2) return true;
	for (int i = 2; i <= sqrt(num); i++)
		if (num % i == 0) return false;
	return true;
}

int main(void) {
	int size;
	cin >> size;
	string res;
	int prime[10001] = {0,};
	for (int k = 2; k <= 10000; k++) {
		if (isPrime(k)) prime[k]=k;
	}

	for (int j = 0; j < size; j++) {
		int num,g1=1,g2=10000;
		cin >> num;
		for (int i = 2; i<= num / 2; i++) {
			if (prime[i] != i) continue;
			if (prime[num - prime[i]] == 0) continue;
			if (g2 - g1 > num - 2 * prime[i]) {
				g2 = num - prime[i];
				g1 = prime[i];
			}
		}
		res += to_string(g1 )+ " " + to_string(g2) +"\n";
	}

	cout << res;
	return 0;
}

제출 언어 c++11

 

 

[풀이 전략]

-매번 수를 입력 받을 떄마다 그 수보다 작은 소수를 구하면 비효율적이라 생각되어

미리 소수를 다 구해놓고 문제를 풀었다.

-에라토스테네스의 체 활용.

-이중 for문 맨 안쪽에 2부터 시작하지 않고 num/2부터 시작해 작아지는 방향으로 풀면 시간이 더 짧게 걸릴 듯 하다.

[다른 사람 풀이]

구하는 방식은 비슷하다.