首先可以特判出 \(15\) 以下的点（其实我还是觉得判 \(12\) 以下就行了）
首先可以发现对于质数 \(p\)，若 \(3p>n\)，那么以 \(p\) 为最小质因子的数一定不会在答案中。
设\[ k=upper\_bound(p+1,p+tot+1,n)-p-1\\ t=upper\_bound(p+1,p+tot+1,n/3)-p-1 \] 可以除去不会使用的质数。
那么答案的上界为 \(n-1-(k-t)\)
接下来我们给出一组构造方案，当明白一组后就会想到更多其他的方案。
考虑到倍数最多的数是 \(2\) 和 \(3\)，所以我们用 \(2\) 与 \(3\) 为基础进行构造。
首先我们取出 \(12\) 和 \(2\)，\(12\) 可以沟通 \(2\) 与 \(3\)。
然后我们将每个可行的质数进行构造，每个数的基本思想是以它的 \(2\)，\(3\) 倍为首位，中间连接它的其他倍数。
然后每个质数这样交错进行就可以形成 \(2p-p......-3p-3q-q-......2q\) 的链。
最后要考虑的就是如何将此链与 \(12\) 那头和 \(3\) 的一边拼接在一起。
可以讨论 \(t\) 的奇偶，若为奇数，那么可以先输出 \(3\) 再将 \(3p\) 拼在一起，再连接 \(6\) 再连接 \(2p\)，最后连 \(12\)。
奇数的情况类似。
构造方法很多，无需（须？）拘泥于一种。
\(code\) ：
#include<bits/stdc++.h> #define gc getchar #define ll long long using namespace std; const int N=5e5+1; template<class I> inline void read(I &x) { int f; char c; for (f = 1,c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc()); x *= f; } int T,n; int v[N+7],p[N+7],tot; void primes(){ for(int i=2;i<N;i++){ if(v[i]==0){ v[i]=i; p[++tot]=i; } for(int j=1;j<=tot;j++){ if(p[j]>v[i]||p[j]>N/i) break; v[i*p[j]]=p[j]; } } } void solve(){ if(n<=7) return puts("3"),puts("2 4 6"),void(); if(n<=9) return puts("4"),puts("2 4 6 8"),void(); if(n<=11) return puts("5"),puts("2 4 6 8 10"),void(); //if(n<=13) return puts("8"),puts("2 4 8 10 12 9 3 6"),void(); //if(n<=14) return puts("9"),puts("2 4 8 10 14 12 9 3 6"),void(); int k=upper_bound(p+1,p+tot+1,n)-p-1; int t=upper_bound(p+1,p+tot+1,n/3)-p-1; cout<<n-1-(k-t)<<endl; memset(v,0,sizeof(v)); v[12]=v[2]=1,printf("12 2 "); for(int i=3;i<=t;i++) if(i&1){ v[p[i]*2]=v[p[i]]=1; printf("%d %d ",p[i]*2,p[i]); for(int j=p[i]*4;j<=n;j+=p[i]) if(!v[j]) v[j]=1,printf("%d ",j); v[p[i]*3]=1,printf("%d ",p[i]*3); } else { v[p[i]*3]=v[p[i]]=1; printf("%d %d ",p[i]*3,p[i]); for(int j=p[i]*4;j<=n;j+=p[i]) if(!v[j]) v[j]=1,printf("%d ",j); v[p[i]*2]=1,printf("%d ",p[i]*2); } if(t&1){ v[3]=1,printf("3 "); for(int i=9;i<=n;i+=3) if (!v[i]) v[i]=1,printf("%d ",i); v[6]=1,printf("6 "); for(int i=4;i<=n;i+=2) if (!v[i]) v[i]=1,printf("%d ",i); } else { v[4]=1,printf("4 "); for(int i=8;i<=n;i+=2) if (!v[i]) v[i]=1,printf("%d ",i); v[6]=1,printf("6 "); for(int i=9;i<=n;i+=3) if (!v[i]) v[i]=1,printf("%d ",i); v[3]=1,printf("3 "); } puts(""); } int main(){ read(T); primes(); while(T--){ read(n); solve(); } return 0; }转载于:https://www.cnblogs.com/Hikigaya/p/11582073.html
相关资源：JAVA上百实例源码以及开源项目