백준 1153 네 개의 소수

백준 1153 네개의 소수

---

오늘은 어느 수를 4개의 소수로 표현하는 문제를 풀어보았다.

• 처음에 문제를 풀기 위해 떠올린 아이디어는 다음과 같다.

  1. 에라토스테네스의 채로 n 보다 작은 모든 소수들을 찾는다.
  2. 이 정렬된 소수들을 백트래킹을 하여 4개의 배열을 채우고, 성공한 배열 4개를 출력해준다.

• 이렇게 푸니 가능한 모든 4개 소수의 조합이 나왔다. 그런데 시간 초과가 나왔고, 이렇게 풀면 안되겠다는 생각을 하게되었다.

• 구글링을 해서 찾은 방법은 다음과 같다.

  • 골드바흐의 추측

• 골드바흐의 추측은, 2보다 큰 모든 짝수는 두개의 소수 합으로 나타낼 수 있다는 추측으로, 누구가 증명했다ㅋㅋ

• 암튼, 이 원리를 이용하기 위해 n이 홀수 이면 2, 3 을 쓰고 n-5 에 대해 두개의 소수의 합을 찾고,

• n이 짝수이면 2,2 를 쓰고 n-4에 대해 두개의 소수 합을 찾으면 되는 것이다.

• 구현은 어렵지 않았는데, 백트래킹을 갈기느라 허비한 시간이 너무 길어서 아쉬웠다!

 for (int i = 0; i < sosu_list.size(); i++)
    {
        int first = sosu_list[i];
        int second = n - first;
        if (sosu_pack.find(second) != sosu_pack.end())
        {
            cout<<first << " " << second << '\n';
            return 1;
        }
    }
    return -1;;