最小互质数

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int maxn = 1e6 + 11;
int a[maxn], vis[maxn];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        // out<<a[i]<<endl;
        for (int j = 2; j * j <= a[i]; j ++) {
            if (a[i] % j == 0) {
                vis[a[i] / j] = 1;
            }
        }
        vis[a[i]] = 1;
    }

    if (vis[1] == 0) {
        cout<<1<<endl;
        return 0;
    }
    if (vis[2] == 0) {
        cout<<2<<endl;
        return 0;
    }

    for (int i = 3; i < 1e6; i ++) {
        for(int j = 2; j * j <= i; j ++) {
            if (i % j == 0) {
                if (vis[j]) {
                    vis[i] = 1;
                    break;
                }
                if (vis[i / j]) {
                    vis[i] = 1;
                    break;
                }
            }            
        }
    }

    for (int i = 1; i < 1e6; i ++) {
        if (vis[i] == 0) {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

将 a 数组中的每一个元素及其除本身与 1 的子因子标记为 一访问。

枚举每一个数，若该元素子因子被标记为 1， 则将至标记为 1。
返回第一个未被标记的元素即为所求结果。