Atkin 筛的论文 第 $1028$ 页上方写：

$\text{Consequently one can compute all the primes up to }N\text{ using }\mathcal O(\dfrac n{\log\log n})\text{ operations.}$

即 因此，可以使用 O(N/loglogN) 次操作来计算 N 以内的所有素数。

但是 Atkin 筛的代码如下：

void atkin_sieve(int n)
{
	cnt=2,prime[1]=2,prime[2]=3;
	if(n==2)
	{
		cnt=1;
		return;
	}
	if(n==3) return;
	int lim=sqrt(n),k;
	for(int i=1;i<=lim;++i)
		for(int j=1;j<=lim;++j)
		{
			k=4*i*i+j*j;
			if(k<=n&&(k%12==1||k%12==5))
				isprime[k]^=1;
			k=3*i*i+j*j;
			if(k<=n&&k%12==7)
				isprime[k]^=1;
			k=3*i*i-j*j;
			if(i>j&&k<=n&&k%12==11)
				isprime[k]^=1;
		}
	for(int i=5;i<=lim;++i)
		if(isprime[i])
			for(int j=i*i;j<=n;j+=i*i) isprime[j]=0;
	for(int i=5;i<=n;++i) if(isprime[i]) prime[++cnt]=i;
}

可以明显发现在：

	for(int i=1;i<=lim;++i)
		for(int j=1;j<=lim;++j)

此处复杂度为 $\lim^2$。而前文赋值 $\lim\leftarrow\sqrt n$，即复杂度为 $\mathcal O(n)$，不为 $\mathcal O(\dfrac n{\log\log n})$。