此算法时间复杂度为$O(\frac{n}{log n})$
为确定机的时间复杂度
但有大约100倍常数

代码如下

#include<bits/stdc++.h>
#define maxnyxzs 100000000
#define maxn 100000000
using namespace std;
bool iff;
inline void SORT(int *st, int *ed) {
	const int base = 1 << 15;
	vector <int> v1[base + 5], v2[base + 5];
	for (int *S = st; S < ed; ++S) {
		v1[(*S) & (base - 1)].emplace_back(*S);
	}
	for (int i = 0; i < base; ++i) {
		for (auto x: v1[i]) {
			v2[x >> 15].emplace_back(x);
		}
	}
	for (int i = 0; i < base; ++i) {
		for (auto x: v2[i]) {
			*st = x, ++st;
		}
	}
}
long long gn(){/*get number*/
	char ch=getchar();
	long long fh=1,x=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')fh=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return (fh==1)?x:-x;
}
long long n;
long long a[maxnyxzs]={0,2},aa[maxnyxzs],hs[maxn];
long long cfs=2/*乘法式的值*/,nc=3/*next_chengfashi 乘法式的下一个质数*/,nci=2/*next_chengfashi_i 乘法式的下一个质数的坐标*/;
long long top=2,dl=1/*duilie_long,队列长度*/ ;
long long tmp;
long long w,m;
void shuru(){
	n=maxn;
}
void clac(){
	while(1){
		////<<"step1"<<endl;
		while(1){
			if(a[top]==-1){
				top--; 
				continue;
			}
			if(top<nci)break;
			tmp=cfs-a[top];
			if(tmp>n)return;
			////<<"--------"<<endl;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
				////("%lld\n",tmp);
				////<<"top:"<<top<<endl;
				////<<"a[top]:"<<a[top]<<endl;
			}
			top--; 
		}
	
		////<<"step2"<<endl;
		tmp=cfs-1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
			////("%lld\n",tmp);
			////<<"top:"<<top<<endl;
			////<<"a[top]:"<<a[top]<<endl;
		}
		////<<"step3"<<endl;
		tmp=cfs+1;
		if(tmp>a[dl]){
			++dl;
			a[dl]=tmp;
			////("%lld\n",tmp);
			////<<"top:"<<top<<endl;
			////<<"a[top]:"<<a[top]<<endl;
		}
		////<<"step4"<<endl;
		top=nci;
		while(1){
			if(a[top]==-1){
				top++;
				continue;
			}
			tmp=cfs+a[top];
			if(tmp>n)return;
			if(tmp>a[dl]){
				++dl;
				a[dl]=tmp;
				////("%lld\n",tmp);
				////<<"top:"<<top<<endl;
				////<<"a[top]:"<<a[top]<<endl;
			}
			if(tmp>cfs*a[nci]-a[dl]){
				cfs*=a[nci];
				for(int i=nci+1;i<=dl;i++){
					if(a[i]%a[nci]==0){
						a[i]=-1;
					}
				} 
				for(int i=nci;a[i]==-1;++i,++nci);
				nci++;
				top=dl; 
				goto step1;
			}
			top++;
		}
		step1:
		////<<"dl:::::"<<dl<<endl;
		top=dl; 
	}
}
long long nn;
void shuchu(){
    for(int i=nci;a[i];++i)
        for(int j=i;a[j];++j)
            hs[++w]=a[i]*a[j];
    SORT(hs+1,hs+w+1);
    int ww=1;
    for(int i=1;i<=dl;i++){
        if(a[i]<a[ww]){
            printf("%lld ",a[i]);
        }
        else if(a[i]==a[ww])++i;
        else ++w;
    }
	////<<endl<<"-----------------"<<endl;

}
int main(){
	shuru();
	clac();
	////("clac over\n");
	shuchu();
	return 0;
}

算法思路和时间复杂度证明

以下方便起见,令$p_1=2<p_2=3<p_3<...$为质数序列，$m=m(n)=π(n)$为小于$n$的质数个数，$w=w(n)$为小于n的非完全合数（定义见下）

本算法主要是通过递推跳过“完全合数”
完全合数和非完全合数定义如下： 对一个合数$n$,令$c=c(n)$为最大的整数使$π_{i=1}^{c}p_i<n$
若存在$1<=k<=c$使$p_k|n$，则称n为完全合数，否则称n为非完全合数

由代码中的递推找到所有质数和非完全合数只需$O(m+w)$（请注意$\sum_{k=1}^{+oo}\frac{1}{π_{i=1}^kp_i}<\sum_{k=1}^{+oo}\frac{1}{k(k-1)}=2$）

而之后我们可以通过$O(w)$的时间复杂度来找到所有非完全合数，再用$O(n^{1/2}+w)$的时间复杂度来排序

然后是$O(m+w)$的输出

现在此算法时间复杂度为$O(m+w+n^{1/2})$ 又$n^{1/2}=o(\frac{n}{log n})=o(m)$
故时间复杂度为$O(m+w)$

下证：$m+w等价于\frac{n}{logn}（n->+oo）$

以下等号按等价号理解
由定义，$m+w=n*π_{i=1}^m{(1-\frac{1}{p_i})}$

令$T=T(n)=π_{i=1}^m{(1-\frac{1}{p_i})}$
我们证明$T<\frac{e^2}{logn}$

$logT=\sum_{i=1}^mlog(1-\frac{1}{p_i})$
由$log(1-x)$的解析性
知它的泰勒级数收敛于它本身
故

$$\begin{aligned} -logT&=\sum_{i=1}^m\sum_{k=1}^{+oo}\frac{1}{kp_i^k}\\ &=\sum_{k=1}^{+oo}\frac{1}{k}\sum_{i=1}^m\frac{1}{p_i^k} \end{aligned}$$

我们估计$$的量级

显然，对于任意的$k>=2$,

$$\begin{aligned} \sum_{i=1}^m\frac{1}{p_i^k} &<= \sum_{i=2}^{m+1}\frac{1}{i}\\ &< \int_{1}^{m+1}\frac{1}{x^k}dx\\ &= \frac{1}{k-1}(1-\frac{1}{(m+1)^{k-1}})\\ &< \frac{1}{k-1} \end{aligned}$$

故

$$\begin{aligned} -logT&=\sum_{i=1}^m\sum_{k=1}^{+oo}\frac{1}{kp_i^k}\\ &=\sum_{k=1}^{+oo}\frac{1}{k}\sum_{i=1}^m\frac{1}{p_i^k}\\ &<\sum_{i=1}^m\frac{1}{p_i}+1 \end{aligned}$$

即

$$\begin{aligned} -logT &=\sum_{k=1}^{+oo}\frac{1}{k}\sum_{i=1}^m\frac{1}{p_i^k}\\ &=\sum_{i=1}^m\frac{1}{p_i}+\theta_n (0<\theta_n<1) \end{aligned}$$

我们只需估计$\sum_{i=1}^m\frac{1}{p_i}$

由熟知结论，$\sum_{i=1}^m\frac{1}{p_i}>loglogn-1$

故$logT<-loglogn+2$
即$T<\frac{e^2}{logn}$
故$m+w=O(nT)=O(\frac{n}{logn})$

我们证明了此算法的时间复杂度绝不可能改进，后人只能优化常数（是的，常数非常大）