[C++] 9020번 골드바흐의 추측

골드바흐의 추측은 예전에 학교 정수론 강의에서 들었었다.

(사실 기억이 어렴풋이 나는거라 자세히는 기억이 안난다.)

 

2보다 큰 짝수는 무조건 두 소수의 합으로 표현이 된다는 것이 골드바흐의 추측이다.

그리고 차이가 가장 적게 나는 방법으로 두 소수를 찾으면 된다.

 

처음에 풀었는데 시간이 1976ms가 나와서 다른 풀이를 찾아봤다. 24ms만 초과했어도 시간초과였다. 

잘못된 방법으로 풀었기 때문에 다른 풀이로 풀었는데 0ms가 나왔다.

문제풀이

처음의 내가 푼 방식의 코드부터 보여주겠다.

#include <iostream> #include <vector> #include <math.h> using namespace std; int testCase, num; int ans1, ans2; bool primeCheck[10001]; // true라면 소수아님. false이면 소수 vector<int> primeVec; int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);          cin >> testCase;     for (int i = 2; i <= 10000; i++) {         if (!primeCheck[i]) {             primeVec.push_back(i);             for (int j = i + i; j <= 10000; j += i) {                 primeCheck[j] = true;             }         }     }     while(testCase--) {         cin >> num;         int diff = 1e10;         for (int i = 0; i < primeVec.size(); i++) {             for (int j = i; j < primeVec.size(); j++) {                 if (primeVec[i] + primeVec[j] == num) {                     int newDiff = abs(primeVec[j] - primeVec[i]);                     if (diff > newDiff) {                         ans1 = primeVec[i];                         ans2 = primeVec[j];                     }                 }             }         }         cout << ans1 << " " << ans2 << "\n";     }     return 0; }

코드는 아래와 같은 로직으로 짰다.

• 1부터 10,000까지의 소수들을 vector에 담아놓는다.
• 각 테스트 케이스마다 숫자를 입력받는다. 그리고 소수 벡터에서 가장 작은 소수 2부터 시작해서 모든 수와 더해보면서 가장 차이가 적게나는 두 소수들을 고른다.

이렇게하면 최악의 경우 2부터 10,000까지의 소수 개수 x (2부터 10,000까지의 소수 개수 - 1) x (2부터 10,000까지의 소수 개수 - 2) x ...

의 시간이 걸린다.

 

처음에는 소수의 개수가 적어서 시간 복잡도에 걸리지 않을 줄 알았는데,

막상 풀어보니 정답은 맞췄지만 시간 복잡도에 너무 아슬아슬하게 걸리지 않았다.

그래서 다른 사람의 풀이를 보아서 다시 풀어보았다.

훨씬 코드도 간단해지고 시간도 0ms가 걸렸다.

 

사용한 STL과 변수

• testCase : 테스트 케이스의 개수
• num : 각 테스트 케이스마다 입력받는 수
• ans1 : ans2와 합해서 num이되는 작은 소수
• ans2 : ans1와 합해서 num이되는 큰 소수
• primeCheck 배열 : 해당 idx의 수가 소수인지 아닌지 판별하는 배열. true일 때 소수가 아니도록 만들었다.

메인함수

 

메인함수에서는 테스트 케이스를 입력받은 후에

2부터 10,000까지 소수인지 아닌지에 대한 정보를 저장해놓는다.

그리고 각 테스트 케이스마다 다음과 같은 로직으로 두 소수를 찾는다.

• ans1과 ans2에 num / 2를 저장해놓는다.
• ans1과 ans2가 둘 다 소수가 될 때까지 ans1는 1을 빼주고 ans2는 1을 더해준다. (ans1이 더 작은 수여야 한다.)

그리고 ans1과 ans2가 소수가 됐다면 두 수를 출력한다.

 

정수론, 수학문제였는데 생각은 쉽게했는데 막상 시간복잡도에 아슬아슬하게 안걸렸던 문제.

이런 문제는 오히려 더 쉬운 방법이 생각이 안나는 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.