C++11(clang++ 3.9) 解法, 执行用时: 173ms, 内存消耗: 13000K, 提交时间: 2020-03-24 22:35:18

#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
#define MAXNUM 1111111
#define ll long long
#define rep(i,start,end) for(int i=start;i<end;i++)
vector<ll> prime;
bool isprime[MAXNUM];
ll n;
void per()
{
	rep(i,1,n+1)
	isprime[i]=1;
	isprime[0]=isprime[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])
		prime.push_back(i);
		for(int j=i*2;j<=n;j+=i)
		isprime[j]=0;
	}
}
vector<int> middle;
int before,before2;
void getit()
{
	middle.clear(),before=before2=-1;
	auto iter=++prime.begin();
	for(;iter!=prime.end();iter++)
	if((*iter*4)<=n)
	middle.push_back(*iter);
	else break;
	auto a=iter;
	int now=0;
	while(iter!=prime.end()&&*iter*2<=n&&*iter*3<=n)
	iter++,now++;
	if((now&1)&&middle.size())
	before2=*(a++);
	if(a!=prime.end()&&*a*2<=n)
	before=*a;
	if(iter!=prime.end()&&*iter*2<=n)
	before=*iter; 
}
int isused[MAXNUM];
void p(int k)
{
	isused[k]=1,printf("%d ",k);
}
void printit(int k)
{
	for(int i=k;i<=n;i+=k)
	if(!isused[i])
	p(i);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		prime.clear();
		per();
		getit();
		rep(i,1,n+1)
		isused[i]=0;
		auto iter2=++prime.begin();
		while(*iter2*4<=n)
		iter2++;
		for(auto iter=iter2;iter!=prime.end();iter++)
		{
			if(*iter==before||*iter==before2)
			continue;
			if(*iter*2<=n)
			isused[*iter*2]=1;
			if(*iter*3<=n)
			isused[*iter*3]=1;
		}
		if(before!=-1)
		{
			isused[before*2]=1;
			printit(before);
			p(before*2);
		}
		if(before2!=-1)
		{
			isused[before2*2]=isused[before2*3]=1;
			p(before2*2);
			printit(before2);
			p(before2*3);
		}
		for(int k:middle)
		{
			p(k*2);
			isused[k*4]=1;
			printit(k);
			p(k*4);
		}
		printit(2);
		bool type=1;
		for(auto iter=iter2;iter!=prime.end();iter++)
		{
			if(*iter==before||*iter==before2)
			continue;
			if(*iter*2<=n&&type)
			p(*iter*2);
			else if(*iter*3<=n&&!type)
			p(*iter*3);
			printit(*iter);
			if(*iter*2<=n&&!type)
			p(*iter*2);
			else if(*iter*3<=n&&type)
			p(*iter*3);
			type=!type;
		}
		printf("1\n");
	}
}