Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 수열 출력 프로그램: 연속된 두 수는 서로소가 아니고, 연속된 세 수는 서로소가 되도록 출력하기

문제 소개

이 튜토리얼에서는 연속된 두 수는 서로소(coprime)가 아니면서, 연속된 세 수는 반드시 서로소가 되도록 수열을 출력하는 프로그램을 C++로 구현하는 방법을 알아봅니다.

문제를 정리하면 다음과 같습니다. 정수 N이 주어졌을 때, 10억(109)보다 작은 N개의 정수를 출력해야 하며, 출력 결과는 아래 두 조건을 동시에 만족해야 합니다.

조건 1. 이웃한 두 수의 최대공약수(GCD)는 1이 아니어야 합니다. 즉, 인접한 두 수는 반드시 공약수를 가져야 합니다.
조건 2. 이웃한 세 수의 최대공약수는 1이어야 합니다. 즉, 연속된 세 수를 모두 나눌 수 있는 공약수는 존재하지 않아야 합니다.

예를 들어 N이 4라고 가정해 보겠습니다. 이때 두 조건을 모두 충족하는 수열은 다음과 같습니다.

6 15 35 14

실제로 gcd(6, 15) = 3, gcd(15, 35) = 5, gcd(35, 14) = 7이므로 이웃한 두 수는 서로소가 아니며, 반면 gcd(6, 15, 35) = 1, gcd(15, 35, 14) = 1이므로 연속된 세 수는 서로소임을 확인할 수 있습니다.

접근 방법

이 문제의 핵심 아이디어는 소수 배열에서 인접한 두 소수의 곱을 수열의 원소로 사용하는 것입니다. 수열의 i번째 원소를 p[i] × p[i+1](여기서 p는 소수 배열)로 정의하면 두 조건이 자연스럽게 성립합니다.

- ar[i] = p[i] × p[i+1]과 ar[i+1] = p[i+1] × p[i+2]는 공통 인수 p[i+1]을 공유하므로, 두 수의 GCD는 절대 1이 될 수 없습니다.
- 연속된 세 수 ar[i], ar[i+1], ar[i+2]를 모두 나누는 소수는 존재하지 않으므로, 세 수의 GCD는 항상 1입니다.

전체 구현 과정은 다음과 같이 진행됩니다.

1. 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 2,000,000 이하의 모든 소수를 미리 구합니다.
2. 인접한 두 소수의 곱이 10억을 넘지 않는 범위까지만 후보 수열을 생성하고, 이미 사용된 곱은 map 자료구조로 중복 여부를 관리합니다.
3. 요청된 개수 N만큼의 원소를 출력하되, 마지막 원소는 마지막 두 원소의 GCD에 2를 곱한 값으로 출력해 조건을 그대로 유지합니다.

C++ 예제 코드

#include <bits/stdc++.h>
using namespace std;
#define limit 1000000000
#define MAX_PRIME 2000000
#define MAX 1000000
#define I_MAX 50000
map<int, int> map1;
int b[MAX];
int p[MAX];
int j = 0;
bool prime[MAX_PRIME + 1];
void sieve(int n){
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++){
        if (prime[p] == true){
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++){
        if (prime[p]) {
            b[j++] = p;
        }
    }
}
int gcdiv(int a, int b){
    if (b == 0)
        return a;
    return gcdiv(b, a % b);
}
//필요한 수열을 출력하는 함수
void print_elements(int n){
    sieve(MAX_PRIME);
    int i, g, k, l, m, d;
    int ar[I_MAX + 2];
    for (i = 0; i < j; i++){
        if ((b[i] * b[i + 1]) > limit)
            break;
        p[i] = b[i];
        map1[b[i] * b[i + 1]] = 1;
    }
    d = 550;
    bool flag = false;
    for (k = 2; (k < d - 1) && !flag; k++){
        for (m = 2; (m < d) && !flag; m++){
            for (l = m + k; l < d; l += k){
                if (((b[l] * b[l + k]) < limit)
                    && (l + k) < d && p[i - 1] != b[l + k]
                    && p[i - 1] != b[l] && map1[b[l] * b[l + k]] != 1){
                    if (map1[p[i - 1] * b[l]] != 1){
                        p[i] = b[l];
                        map1[p[i - 1] * b[l]] = 1;
                        i++;
                    }
                }
                if (i >= I_MAX) {
                    flag = true;
                    break;
                }
            }
        }
    }
    for (i = 0; i < n; i++)
        ar[i] = p[i] * p[i + 1];
    for (i = 0; i < n - 1; i++)
        cout << ar[i] << " ";
    g = gcdiv(ar[n - 1], ar[n - 2]);
    cout << g * 2 << endl;
}
int main(){
    int n = 4;
    print_elements(n);
    return 0;
}

실행 결과

6 15 35 14

마무리

이처럼 인접한 소수들의 곱을 활용하면 복잡한 탐색 과정 없이도 주어진 조건을 만족하는 수열을 효율적으로 생성할 수 있습니다. 에라토스테네스의 체로 소수를 미리 구해 두기 때문에 소수 판별 비용이 크게 줄어들고, map을 통한 중복 관리 덕분에 안정적으로 원소를 확장할 수 있어 큰 N에 대해서도 좋은 성능을 보입니다.