# Harder Gcd Problem

``````#includebits/stdc++.h
using namespace std;
typedef long long ll;
typedef pairint,intP;
const int inf = 0x7f7f7f7f;
const int N = 2e5+10;
const ll mod = 1e9+7;
const double PI = 3.14;

char ch=getchar();int x=0,f=1;
while(ch'0'||ch'9'){if(ch=='-')f=-1;ch=getchar();}
while('0'=chch='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int random(int n){return(ll)rand()*rand()%n;}

int prime[N],vis[N],cnt = 0;
vectorintv[N];
vectorint::iterator it;

void init(){
for(int i = 2;i  N;i++){
if(!vis[i]) prime[cnt++] = i;
for(int j = 0;j  cnt;j++){
if(i*prime[j] = N) break;
vis[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
}
}
}

int ans[N];

void solve(){
int m = upper_bound(prime,prime+cnt,n/2)-prime;
memset(vis,0,sizeof vis);
int cnt = 0;
for(int i = m-1;i = 0;i--){
for(int j = prime[i];j = n;j += prime[i]){
if(vis[j] || j == 2*prime[i]) continue;
vis[j] = 1;
ans[++cnt] = j;
}
if(cnt1){
ans[++cnt] = 2*prime[i];
vis[2*prime[i]] = 1;
}
}
printf("%d\n",cnt/2);
for(int i = 1;i = cnt;i += 2){
printf("%d %d\n",ans[i],ans[i+1]);
}
}
int main(){
//srand((unsigned)time(0));
//freopen("out.txt","w",stdout);
//freopen("in.txt","r",stdin);
init();//预处理
/*
for(int i = 0;i  30;i++){
printf("%d,",prime[i]);
}
*/
// cout(61)endl;
while(t--){
solve();
}
return 0;
}

``````
• 星秀
• 1:24:00