数据过水

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map> 
using namespace std;
inline char gc(){
	static char BB[1<<20],*S=BB,*T=BB;
	return S==T&&(T=(S=BB)+fread(BB,1,1<<20,stdin),S==T)?EOF:*S++;
} 
inline int read(){
	int x=0;char ch=gc();
	while(ch<48) ch=gc();
	while(ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=gc();
	return x;
}
bool vis[100000010];
signed main(){
	int T=read();
	while(T--){
		memset(vis,0,sizeof vis);
		int n=read(),g=0;bool flag=1;
		for(int i=1,x;i<=n;i++){
			x=read();g=__gcd(g,x);
			if(!flag) continue;
			for(int j=1;j*j<=x;j++){
				if(x%j==0){
					if((j>1?vis[j]:0)||vis[x/j]) flag=0; 
					vis[j]=vis[x/j]=1;
				}
				if(!flag) break;
			}
		}
		cout<<((g==1&&flag)||n==2?"Yes\n":"No\n");
	}
	return 0;
}

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 目标：生成 500,000 个小于等于 10^8 的最大质数
const int MAX_VAL = 100000000;
const int COUNT = 500000;
const int RANGE = 10000000; // 向前搜索的范围，1000万足够找到50万个质数

bool not_prime[RANGE + 10];
vector<int> primes;

int main() {
	freopen("hack.in","w",stdout); 
    // 优化 I/O，虽然对生成器不重要，但习惯使然
    ios::sync_with_stdio(false);
    cout.tie(NULL);

    int start_num = MAX_VAL - RANGE;
    
    // 1. 简单的区间筛法
    // 只需要筛到 sqrt(1e8) = 10000 的质数来筛区间
    vector<int> small_primes;
    for (int i = 2; i * i <= MAX_VAL; ++i) {
        bool is_p = true;
        for (int p : small_primes) {
            if (p * p > i) break;
            if (i % p == 0) { is_p = false; break; }
        }
        if (is_p) small_primes.push_back(i);
    }

    // 2. 标记区间 [start_num, MAX_VAL]
    for (int p : small_primes) {
        // 找到区间内第一个 p 的倍数
        long long start_mult = (long long)(start_num + p - 1) / p * p;
        if (start_mult < 2 * p) start_mult = 2 * p;

        for (long long j = start_mult; j <= MAX_VAL; j += p) {
            not_prime[j - start_num] = true;
        }
    }

    // 3. 收集最大的 500,000 个质数
    for (int i = RANGE; i >= 0; --i) {
        if (!not_prime[i] && (start_num + i) > 1) {
            primes.push_back(start_num + i);
            if (primes.size() == COUNT) break;
        }
    }

    // 4. 输出 Hack 数据
    cout << "1" << endl; // T
    cout << primes.size() << endl; // n
    for (int i = 0; i < primes.size(); ++i) {
        cout << primes[i] << (i == primes.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}