c - 生成一个包含相邻互质对的列表

Question

给定 N 个元素，使得从 1 到 N-1 的每个元素仅出现一次(除了一个)。你的任务非常非常简单。以任意顺序排列这些元素，使得每对相邻元素互质。假设我们有 5 个元素 A1 、 A2 、 A3 、 A4 、 A5 ，所需的顺序是任意顺序 B1 、 B2 、 B3 、 B4 、 B5 ，这样。

gcd(B1,B2) = gcd(B2,B3) = gcd(B3,B4) = gcd(B4,B5) =1.

输入:

输入的第一行包含一个整数 N，表示元素的数量。输入的下一行包含 N 个空格分隔的整数，表示 N 个元素。

输出:

输出由 N 个空格分隔的整数组成，表示根据上述条件的有效序列。

限制:

N<=5*10^6

A[i] <= [common sense]

所有值均严格符合约束条件。

我尝试过这个。请提出更好的算法。

#include<stdio.h>
#include<stdlib.h>
int coprime(int num1 , int num2)
 {
     while(num2%num1!=0)
     {
          int rem= num2%num1;
          num2=num1;
          num1=rem;
     }
     return (num1==1);
}

int main()
{
    long int *arr , n , i=0 ,j ,k , p,flag=0,t;
    puts("enter the no of elements");
    scanf("%ld" ,&n);
    arr=(long int*)malloc(n*sizeof(long int));
    p=n;

    while(i<n)
    {
        scanf("%ld",&arr[i]);

        if(arr[i]==0)
            break;
        i++;
    }

    for(i=0 ; i<n ; i++)
    {
        if(!flag)
            p--;
        k=arr[p];

        for(j=0; j<n; j++)
        {
            if(coprime(k,arr[j]))
            {

                if(coprime(k,arr[j+1]))
                {
                    for(t=n; t>j+1 ; t--)
                    {
                        arr[t]=arr[t-1];
                    }
                    arr[j+1]=k;
                    j++;
                }
                else if(j>0&&coprime(k,arr[j-1]))
                {
                    for(t=n; t>j ; t--)
                    {
                        arr[t]=arr[t-1];
                    }
                    arr[j]=k;

                }
                flag=1;
                break;
            }
        }
    }

    for(i=0; i<n; i++)
        printf("%ld " ,arr[i]);

    return 0;
}

Answer 1

这是一个非常简单的解决方案:假设出现两次的数字是x。那么答案就是{x, 1, 2, 3, ..., n - 1}。为什么它有效？对于任何 x，gcd(x, 1) = 1 和对于任何 agcd(a, a + 1) = 1/。因此，这个顺序是正确的。