[BOJ] 9020 - 골드바흐의 추측
문제
풀이 과정
저번에 소수 문제를 풀어봤으니 이어서 소수 카테고리를 마저 풀기로 했다.
지난 번에 2581번에서 썼던 소수 구하는 알고리즘을 다음과 같이 조금 개선했다.
#include <iostream>
#include <vector>
bool isPrime(int n)
{
if (n == 2)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int j = 3; j * j <= n; j+= 2)
{
if (n % j == 0)
return false;
}
return true;
}
2가 아닌 짝수일 경우 절대 소수가 아니므로
반복문을 돌리기 전에 n이 2일 때는 true를 return하고, 짝수일 때는 false를 return하도록 바꿔주고 3에서부터 2씩 더해가면서 n을 나눠봄으로써 반복 횟수를 줄여봤다.
이제 2보다 큰 짝수가 주어지면 그 짝수의 소수 인수를 구해야 한다.
그런데 문제에서 n의 골드바흐 파티션이 여러 쌍인 경우 두 소인수의 차가 가장 작은 경우만 출력하라고 했으므로, n을 2로 나눈 지점부터 시작하고 찾으면 끝내는 식으로 코드를 짜는 것이 바람직할 것으로 생각했다.
n은 짝수이기 때문에 무조건 2로 나누어 떨어진다.
이 나눠진 두 조각을 left와 right라고 하자. 최초에는 left와 right가 동일하다.
만약 left가 2가 아닌 짝수인 경우 절대 소수일 수 없으므로
left에서는 1을 빼주고 right에서는 1을 더해준다.
(left가 2인 경우에는 4 = 2x2로, 파티션이 바로 끝난다.)
그럼 두 수는 홀수가 되고, 소수일 가능성이 생긴다.
이제 isPrime 함수를 거쳐 left와 right가 소수인지 확인하고, 둘 다 소수라면 가장 차가 적은 경우의 파티션을 찾았다.
둘 다 소수가 아닌 경우, left에서는 2를 빼고 right에서는 2를 더해가면서 다시 두 수가 소수인지를 검사한다. 두 수 모두 소수일 경우, 파티션을 찾았으니 반복문을 끝내면 된다.
이를 그대로 소스코드로 작성하면 다음과 같다.
파티션 과정을 진행하는 goldbachPartition 함수에서 소인수 2개를 return하기 위해 results라는 배열을 만들어 넣어주었다.
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int n)
{
if (n == 2)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int j = 3; j * j <= n; j+= 2)
{
if (n % j == 0)
return false;
}
return true;
}
vector<int> goldbachPartition(int n)
{
int left, right;
vector<int> results; // 결과를 담은 배열
results.resize(2);
left = right = n / 2;
if (left % 2 == 0 && left != 2) // 2로 나눈 것이 2가 아닌 짝수일 경우 절대 소수가 될 수 없으므로
{
left -= 1;
right += 1;
}
if (isPrime(left) && isPrime(right)) // 소수인지 확인해서 둘 다 소수이면 파티션 성공
{
results[0] = left;
results[1] = right;
}
else
{
while (left >= 2)
{
left -= 2;
right += 2;
if (isPrime(left) && isPrime(right)) // 소수인지 확인해서 둘 다 소수이면 파티션 성공, 반복문 끝냄
{
results[0] = left;
results[1] = right;
break;
}
}
}
return results;
}
int main(void)
{
int test = 0;
cin >> test;
for (int t = 0; t < test; t++)
{
int n = 0;
cin >> n;
vector<int> results;
results = goldbachPartition(n);
printf("%d %d\n", results[0], results[1]);
}
return 0;
}
좀 더 생각해보면 더 효율적으로 짤 수도 있을 것 같으나 귀찮으니 패쓰~~~