[C/C++ 백준 6588번] 골드바흐의 추측 (Silver 1)

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

문제를 맞히기보다는, 소수 판정에 대해 짧고 간결한 코드를 연습한다는 느낌으로 풀어보자.

 

소수 판정시 sqrt(n)까지의 수들까지만, 그리고 홀수의 경우만 나눠보면 시간을 크게 줄일 수 있는 것 같다. 이 문제는 홀수만 판별하면 되서 짝수인 경우는 생각 안했다. +골드바흐의 추측이 틀릴 것은 아예 생각을 안했다.

 

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
bool isPrime(int n){
	int root = sqrt(n);
	for(int i=3; i<=root; i+=2){
		if(n%i==0)
			return false;
	}
	return true;
}
void gold(int n){
	for(int i=3; i<=n/2; i+=2){
		if(isPrime(i) && isPrime(n-i)){
			printf("%d = %d + %d\n",n,i,n-i);			
			break;
		}
	}
}
int main(void){
	int n;
	while(1){
		scanf("%d", &n);
		if(n==0)
			break;
		else
			gold(n);
	}
}