https://www.acmicpc.net/problem/6588
6588번: 골드바흐의 추측
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰
www.acmicpc.net
🔔 문제 :
짝수 정수 n ( 6 <= n <= 1,000,000) 를 n = a + b 형식으로 만들어라.
단 a와 b는 홀수인 소수이다.
🔔 Kick Point :
소수인지 아닌지를 판정하는 함수를 만들었다.
이때 시간복잡도 ( √O ) 를 두기 위해 1 ~ √N 까지만 판단한다.
bool isPrime(int n) {
// 2부터 루트 n까지 공약수가 있는지 확인
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
그럼에도 시간 초과가 나길래 확인해 보았더니, 줄바꿈시 cout << endl 사용보다 cout << '\n' 이
더욱 속도를 빠르게 해줌을 알게됐다.
🔔 Code :
#include <iostream>
using namespace std;
bool isPrime(int n) {
// 2부터 루트 n까지 공약수가 있는지 확인
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int main( ){
// cout , cin 최적화를 위한 코드(?)
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int n = 1;
int odd_i, odd_j;
while(n) {
cin >> n;
//odd_i = 3; odd_j = n - 3; // defalut
for(int i = 1; i < n/2 ; i++){
odd_i = 2 * i + 1;
odd_j = n - odd_i;
if (isPrime(odd_i) and isPrime(odd_j))
{
cout << n << " = " << odd_i << " + " << odd_j << "\n";
break;
}
}
if (odd_i > odd_j) { cout << "Goldbach's conjecture is wrong." << "\n"; }
}
}