猫史档案馆

我是zzh

Lv.1

其实我是埃氏筛

签名:埃氏筛多线程怎么写啊（崩溃）

在 Python 有趣代码 中回复

其实第二个直接用len函数就行了......

2023-10-31T21:31:44 点赞:2

在 关于埃氏筛的高度优化2 中回复

忘讲时间复杂度证明了，在这里补充一下吧

我们首先定义 π(n)为n以内素数的个数,p_i为第i个素数。则能根据代码给出以下式子：

π(n)+ ∑^pi<=sqrt(n)_i=2 (n-p_i²)/(2*p_i)

即 π(n)+(n-9)/6+(n-25)/10+......+(n-p_i²)/(2*p_i)

整理得 π(n)+(1/2)*(n/3+n/5+......+n/p_i-3-5-......-p_i)

π(n)+(n/2)*(1/3+1/5+......+1/p_i)-(1/2)*(3+5+......+p_i)

由于 1/3+1/5+....+1/pi这个式子的值近似于1，所以直接当作1来看

后面的(3+5+......+pi)则直接当作有π(sqrt(n))/2组(3+p_i)来看

π(n)+n/2-π(sqrt(n))/2*(3+p_i)

已知π(n)的值近似于n/in(n)，p_i近似于sqrt(n)

则有

n/in(n)+n/2-sqrt(n)/(4*in(sqrt(n)))*(3+sqrt(n))

由于in不方便通分，而log求出的值于它相似，因此，用log来替换in

n/log n+n/2-sqrt(n)/(4*log sqrt(n))*(3+sqrt(n))

因为log n+log m=log(n*m)

所以4*log sqrt(n)=2*log n

n/log n +n/2 -sqrt(n)*(3+sqrt(n))/(2*log n)

通分得(n+n log n-3sqrt(n))/(2*log n)

仅保留次数最高的一项，再次化简得到n/2

因此优化后的埃氏筛时间复杂度为O(n/2)

2023-11-01T16:30:15 点赞:0

在 新作品——中国 中回复

可惜我只会写Python啊

2023-11-01T17:36:28 点赞:0