Chương trình C++ in dãy số thỏa mãn điều kiện coprime đặc biệt

In N số nguyên < 10^9 sao cho: không có 2 số liên tiếp nào nguyên tố cùng nhau (coprime), nhưng mọi 3 số liên tiếp đều nguyên tố cùng nhau.

Ví dụ N=4 → 6 15 35 14.

Giải pháp: dùng sàng Eratosthenes sinh số nguyên tố. Xây dựng dãy bằng cách nhân các cặp số nguyên tố liên tiếp, đảm bảo điều kiện GCD.

Ví dụ mã nguồn

#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;
}

Kết quả đầu ra

6 15 35 14