题意：
存在一个n位的a序列 经过下列操作
遍历这个a序列 如果
1 ai 是素数 那么增加preime[ai] （第ai位素数）
2 ai 不是素数 那么增加最大因子 （自己不算）
将新的序列作为b 显然 有2n个元素
给出b序列 要求a序列
显然要筛出第几个素数是什么 和 最大因子 （直接求最大因子比较麻烦 可以求最小因子 然后除一下就是最大因子）
两种转换方式分别为
1 素数转素数 小转大
2 非素数转 素数或者非素数都可以 大转小
假设先求出条件一的数
那么可能 遇到条件2的素因子 将素因子作为a序列进行转换了 所以排除这种做法
假设先求出条件二的数
注意要从大往小遍历 那么遇到非素数 直接输出即可 然后顺便删除其最大素因子 没有任何冲突
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=5000000+5; const int M=2*500000+5; int n,m,pre[N],minn[N],prime[N],mp[N],cnt,x,maxx; void init() { CLR(minn,0x3f); rep(i,2,N) if(!prime[i]) { pre[++cnt]=i; for(int j=2*i;j<=N;j+=i) prime[j]=1,minn[j]=min(minn[j],i); } } int main() { init(); RI(n); rep(i,1,2*n) { RI(x);mp[x]++;maxx=max(maxx,x); } repp(i,maxx,1) if(prime[i]) while(mp[i])printf("%d ",i),mp[i]--,mp[i/minn[i]]--; rep(i,1,maxx) while(mp[i]) printf("%d ",i),mp[i]--,mp[pre[i]]--; return 0; }