楼上抛出的问题很有意思啊。

设函数$\varphi \left(x\right)$ 等于不大于x的全体质数个数，则时间复杂度可以表示为$O\left(\varphi \right(\lfloor \sqrt{N}\rfloor \left)\right)$ 。

因为算法的关键路径：

用小于K的所有质数去除N

（其中$K=\lceil \sqrt{N}\rceil$ ）

可通过一个循环体来实现，循环次数 $T=\varphi (K-1)$ 。

自然地，时间复杂度就为$O\left(\varphi \right(\lceil \sqrt{N}\rceil -1\left)\right)$ = $O\left(\varphi \right(\lfloor \sqrt{N}\rfloor \left)\right)$ 。

PS: 这里还涉及一个数据循环依赖的问题，我们姑且认为程序事先知道小于K的所有质数。

那么问题来了，$\varphi \left(x\right)$ 是个什么样的函数呢？似乎黎曼等学者曾经研究过相关问题，过于深奥，这就愁坏了我个非数学专业的。

不过，单看上界$\varphi \left(x\right)\le x$ 必然成立，有$O\left(\varphi \right(x\left)\right)=O\left(x\right)$ ，于是得到时间复杂度为：

$O\left(\sqrt{N}\right)$ 。

虽然在全体正整数集上不清楚$\varphi \left(x\right)$，但在有限范围内还是可以画出图像，观察得到N<=1e6总体呈线性增长，但斜率小于1。也就是说，这个算法可以作为同样具有$O\left(\sqrt{N}\right)$ 复杂度的暴力解法的系数优化版本。

但是这个算法实用嘛？前面说过，存在数据的循环依赖，不利于计算机去算。如果打表的话，优势似乎就没了。。。