思路

题目要求找到最小的不小于2的整数x，使得x和数组中至少一个数互质。两个数互质的意思就是它们的最大公约数为1。 我们直接从小到大枚举x，从2开始依次验证。对于每一个x，遍历数组里面所有元素，只要找到任意一个数字和x的gcd等于1，就直接输出当前x，这就是答案。 需要实现辗转相除法的gcd函数，用来计算两个数的最大公约数。按照这个顺序枚举，第一个满足条件的x，自然就是最小的。

重点: 为什么不会超时呢

因为 ai<1e18 那么它最多有16个质数因子 因为2*3*5*7*...*53>1e18 为什么是质因子 因为如果2是这n个数的因子 那2的倍数也肯定是的 所以我们用质因子来判断x要枚举的上限 发现很小 直接暴力 枚举x从2到53即可 或者找到就break 时间复杂度为O(n)

#include <stdio.h>

long long gcd(long long a, long long b)
{
    while(b != 0)
    {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        long long a[200005];
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
        }
        int found = 0;
        long long ans_x;
        for(long long x = 2; found == 0; x++)
        {
            for(int i = 1; i <= n; i++)
            {
                if(gcd(x, a[i]) == 1)
                {
                    ans_x = x;
                    found = 1;
                    break;
                }
            }
        }
        printf("%lld\n", ans_x);
    }
    return 0;
}