백준 1153번 [네 개의 소수](C++)-yes6686- 티스토리

백준 문제 풀이: 1153 [네 개의 소수]

---

문제 링크: https://www.acmicpc.net/problem/1153

문제 설명:

자연수 n이 주어졌을 때, n을 네 개의 소수의 합으로 표현할 수 있는지 판단하고, 가능하다면 네 개의 소수를 출력하는 문제입니다. 여러 정답이 있을 경우 그중 하나만 출력하며, 불가능한 경우 -1을 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001];
int p[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 에라토스테네스의 체를 이용하여 소수 판별
    for (int i = 1; i <= n; i++) arr[i] = i;
    for (int i = 2; i * i <= n; i++) {
        if (arr[i] == 0) continue;
        for (int j = i * i; j <= n; j += i) {
            arr[j] = 0;
        }
    }

    // 소수를 배열 p에 저장
    int s = 0;
    for (int i = 2; i <= n; i++) {
        if (arr[i]) {
            p[s++] = i;
        }
    }

    // 네 개의 소수로 합을 만들 수 있는지 확인
    for (int i = 0; i < s; i++) {
        for (int j = i; j < s; j++) {
            for (int t = j; t < s; t++) {
                for (int h = t; h < s; h++) {
                    if (n == p[i] + p[j] + p[t] + p[h]) {
                        cout << p[i] << ' ' << p[j] << ' ' << p[t] << ' ' << p[h];
                        return 0;
                    }
                    if (n < p[i] + p[j] + p[t] + p[h]) break;
                }
            }
        }
    }

    // 네 개의 소수로 합을 만들 수 없는 경우
    cout << -1;
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 에라토스테네스의 체로 소수를 구하고, 네 중첩 루프를 사용하여 네 개의 소수 합이 n과 같은지 확인합니다.
• 구현 세부사항:
  • 에라토스테네스의 체로 소수 판별 후, 소수를 배열 p에 저장
  • 네 개의 소수를 중첩 루프로 조합하여 합이 n과 같은지 검사
  • 최초로 조건을 만족하는 조합을 발견하면 출력 후 종료
• 시간 복잡도: O(n log log n) + O(s^4)
  • 에라토스테네스의 체: O(n log log n)
  • 네 중첩 루프: O(s^4), s는 소수의 개수

---

결과

주어진 n에 대해 네 개의 소수로 합을 표현할 수 있으면 이를 출력하고, 불가능한 경우 -1을 출력합니다. 에라토스테네스의 체와 완전 탐색을 통해 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!