차이가 n인 두 합성수를 찾는 C++ 프로그램

하나의 숫자 n이 주어졌을 때, 두 수의 차가 정확히 n이 되도록 하는 두 개의 합성수(소수가 아닌 수) a와 b를 찾아야 합니다. 즉, 다음 조건을 만족하는 a와 b를 구하는 문제입니다.

a - b = n

예를 들어 입력이 n = 512라면, 출력은 5120과 4608이 됩니다.

해결 접근 방식

이 문제는 매우 간단한 수학적 아이디어로 해결할 수 있습니다. 바로 10 × n과 9 × n을 출력하는 것입니다.

print 10*n and 9*n.

왜 이 방법이 성립할까?

그 이유는 다음과 같습니다.

• 두 수의 차: (10 × n) − (9 × n) = n 이므로 차이 조건을 항상 만족합니다.
• 합성수 조건: 어떤 양의 정수 n에 대해서도 10 × n은 10을, 9 × n은 9를 약수로 가지므로 두 수 모두 항상 합성수입니다.

따라서 별도의 소수 판별 과정 없이도 항상 올바른 답을 구할 수 있습니다.

구현 예제

다음은 위 아이디어를 C++로 구현한 코드입니다.

#include<bits/stdc++.h>
using namespace std;
void solve(int n){
    cout<<10*n<<", "<<9*n;
}
int main(){
    int n = 512;
    solve(n);
}

입력

512

출력

5120, 4608

시간 복잡도

이 알고리즘은 단순히 곱셈과 출력만 수행하므로 시간 복잡도는 O(1)입니다. 입력 크기와 무관하게 일정한 시간 안에 결과를 얻을 수 있습니다.