在试验除法算法中，确定数字是否n为质数可能需要做的最多工作是测试质数的约数sqrt(n)。

当n是素数或几乎相同大小的两个素数的乘积（包括素数的平方）时，会遇到最坏的情况。如果n具有两个以上的素数，或两个大小不同的素数，则其中至少一个比少得多sqrt(n)，因此，即使是所有这些数字所需的累加功（构成所有数字的绝大部分，直到N，足够大N）相对微不足道，我将忽略这一点，并以虚假的结论来确定复合数而不做任何工作（两个近似相等的素数的乘积数量很少，因此尽管它们各自的成本与相似数的素数一样多）大小，这完全是一件微不足道的工作）。

那么，对素数的测试需要做多少工作N？

根据素数定理，素数<= n为（对于n足够大的情况）约为n/log n（是n/log n + lower order terms）。相反，这意味着第 k 个素数（对于 k 不太小）约为k*log k（+低阶项）。

因此，测试第 k 个素数需要将试验除以pi(sqrt(p_k))近似2*sqrt(k/log k)素数。总结一下，k <= pi(N) ~ N/log N得出4/3*N^(3/2)/(log N)^2的结果总计大致为除法。因此，通过忽略组合，我们发现直到N通过试算（仅使用质数）找到质数为Omega(N^1.5 / (log N)^2)。仔细分析复合材料可以发现它是Theta(N^1.5 / (log N)^2)。使用轮子可以减少常数因子，但不会改变复杂性。

另一方面，在筛子中，每种复合物以至少一个质数的倍数被划掉。根据您是否在某处2*p或某处开始交叉p*p，复合材料被交叉的次数取决于其具有不同的主要因子或不同的主要因子<= sqrt(n)。由于任何数字最多都有一个素数超过sqrt(n)，因此相差并不大，因此对复杂度没有影响，但是很多数字中只有两个素数（或者三个素数大于sqrt(n)），因此运行时间明显不同。无论如何，一个数`n

0只有几个不同的素数，一个简单的估计表明，不同的素数的数量受lg n（base-2对数）的限制，所以过筛数的上限是N*lg N`。

通过不计算每个复合物被剔除的频率，而是计算每个质数被剔除的倍数，就像IVlad所做的那样，很容易发现交叉的数量实际上是Theta(N*log log N)。同样，使用轮子不会改变复杂性，但会减少常数因子。但是，这里的影响比试用部门更大，因此至少应该跳过偶数操作（除了减少工作量之外，还减少了存储大小，因此提高了缓存的位置）。

因此，即使不考虑除法比加法和乘法更昂贵，我们也会看到筛子所需的操作数比试验除法所需的操作数小得多（如果限制不太小）。

总结：
试算法通过分割素数来做徒劳的工作，而筛子则通过反复划开合成物来做无效的工作。质数相对较少，但复合数很多，因此人们可能会以为试验部门浪费更少的工作。
但是：复合材料只有很少的不同素数因素，而下面有许多素数sqrt(p)。