Số lần chèn tối thiểu để mảng trở thành mảng nguyên tố cùng nhau trong C++

Cho một mảng N phần tử. Cần tìm số lần chèn tối thiểu để mảng trở thành mảng nguyên tố cùng nhau (co-prime array). Trong mảng co-prime, GCD của mọi hai phần tử liên tiếp là 1. Cần in ra mảng sau khi chèn.

Ví dụ: {5, 10, 20} không phải mảng co-prime. Chèn 1 giữa (5,10) và (10,20) sẽ thành {5, 1, 10, 1, 20}.

Thuật toán

taoMangCoPrime(arr, n):
    bắt đầu
        count := 0
        cho i từ 1 đến n, làm
            nếu gcd(arr[i], arr[i-1]) != 1, thì tăng count 1
        kết thúc
        hiển thị count
        hiển thị arr[0]
        cho i từ 1 đến n, làm
            nếu gcd(arr[i], arr[i-1]) != 1, thì hiển thị 1
            hiển thị arr[i]
        kết thúc
    kết thúc

Ví dụ mã C++

#include <iostream>
#include <algorithm>
using namespace std;

int taoMangCoPrime(int arr[], int n){
    int count = 0;
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            count++;
        }
    }
    cout << "Số điểm chèn: " << count << endl;
    cout << arr[0] << " ";
    for(int i = 1; i < n; i++){
        if(__gcd(arr[i], arr[i - 1]) != 1){
            cout << 1 << " ";
        }
        cout << arr[i] << " ";
    }
}

int main() {
    int A[] = {2, 7, 28};
    int n = sizeof(A)/sizeof(A[0]);
    taoMangCoPrime(A, n);
}

Kết quả đầu ra

Số điểm chèn: 1 2 7 1 28