C++로 길이가 n인 연속된 합성수 구간 찾기

문제 개요

하나의 숫자 n이 주어졌을 때, 구간에 포함된 모든 수가 합성수이면서 구간의 길이가 정확히 n이 되는 양의 정수 범위를 찾아야 합니다. 조건을 만족하는 구간이 여러 개 존재한다면 그중 아무거나 하나만 출력하면 됩니다. 여기서 합성수(composite number)란 1과 자기 자신 외에 최소 하나 이상의 약수를 가지는 수를 의미합니다.

접근 방법: 팩토리얼의 성질 활용하기

구간의 길이가 n이므로, 첫 번째 수를 a라고 하면 나머지 수들은 a + 1, a + 2, …, a + n − 1이 되고, 이 모든 수가 합성수여야 합니다.

이 문제는 팩토리얼의 성질을 이용하면 매우 우아하게 해결할 수 있습니다. 양의 정수 p에 대해 p!는 2, 3, 4, …, p를 모두 약수로 가집니다. 따라서 p! + i는 항상 i를 약수로 가지므로 반드시 합성수가 됩니다. 즉,

p! + 2, p! + 3, …, p! + p 는 모두 합성수입니다.

결국 우리가 찾는 구간은 [p! + 2, p! + p] 형태가 됩니다. 실제 코드에서는 안전 마진을 두고 (n + 2)!을 기준으로 삼아, 시작점을 (n + 2)! + 2로 잡고 끝점을 시작점 + n − 1로 계산합니다.

예제 코드

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0)
        return 1;
    return n * fact(n - 1);
}

void showRange(int n) {
    int a = fact(n + 2) + 2;  // 구간의 시작
    int b = a + n - 1;        // 구간의 끝
    cout << "[" << a << ", " << b << "]";
}

int main() {
    int n = 3;
    showRange(n);
}

실행 결과

[122, 124]

결과 검증

n = 3일 때 (n + 2)! = 5! = 120이므로 구간은 [122, 124]가 됩니다. 각 수를 분해해 보면 다음과 같습니다.

• 122 = 2 × 61
• 123 = 3 × 41
• 124 = 4 × 31

세 수 모두 1과 자기 자신 외의 약수를 가지므로 합성수이며, 길이가 3인 조건을 정확히 만족합니다.

주의 사항

팩토리얼은 값이 매우 빠르게 커지기 때문에 n이 조금만 커져도 int 자료형의 표현 범위를 초과할 수 있습니다. 실제 구현 시에는 long long 같은 더 큰 자료형을 사용하거나, n이 큰 경우 오버플로우 처리 방안을 함께 고려해야 합니다.