筛法

[Ir1d]

https://oi-wiki.org/math/sieve/

[H-J-Granger]

敢问怎么没有说著名的the Meissel, Lehmer, Lagarias, Miller, Odlyzko method

[Ir1d]

@H-J-Granger 蒟蒻不会啊.. 欢迎大佬来补充

[H-J-Granger]

@Ir1d
@H-J-Granger 蒟蒻不会啊.. 欢迎大佬来补充

可是蒟蒻我也不会啊

[war1111]

fi表示i的约数和"建议这里加一个逗号或空格"gi表示i的最小质因子的...

[war1111]

后面是1+p+p^2+...吗？

[zmxqs]

那个埃拉托斯特尼筛法有问题。

int j=i*i

你确定是ii？筛倍数应该是2i才对啊

[ouuan]

若 $i$ 是质数，则 $i-1$ 必为合数

$3$ 是质数 $2$ 不是合数。

因而 $(i-1)(i+1)=i^2-1$ 亦为合数

不管 $i$ 是不是质数，只要大于 $2$， $i^2-1$ 都是合数，没有什么“因而”，也和从 $i^2$ 开始筛的原因无关。

且已被 $i-1$ 的质因子（均小于 $i$）筛去至少一次

不一定是 $i-1$ 的质因子，是被筛的数的小于 $i$ 的质因子。

正确的解释注释里写了，下面的评论里也有。

[gaochenyi]

@ouuan 感谢指正

[zmxqs]

那个所谓的什么 $p+p^1+p^2+…+p^k$那$k=?$

[Dev-XYS]

@zmxqs

那个埃拉托斯特尼筛法有问题。

int j=i*i

你确定是i_i？筛倍数应该是2_i才对啊

如果一个合数是i乘一个比i小的数，那么它之前已经被一个比i小的素数筛过了。

[h56983577]

@zmxqs
那个埃拉托斯特尼筛法有问题。

int j=i*i

你确定是ii？筛倍数应该是2i才对啊

我同意这位的说法，很多时候i * i会溢出，这会导致给数组传入一个负值做下标

[Marcythm]

@zmxqs
那个埃拉托斯特尼筛法有问题。
int j=i*i
你确定是i_i？筛倍数应该是2_i才对啊

我同意这位的说法，很多时候i * i会溢出，这会导致给数组传入一个负值做下标

我认为 @zmxqs 的说法是错的，您提出的问题和他提出的问题其实是两个完全不一样的东西好吗..
至于您提出的问题，我认为 把 j 的类型改成 long long 就好了。求一个好心人来开 pr（

[TravorLZH]

Mertens第二定理的证明可以看这篇文章

[oujunsong]

感觉 筛法求约数个数 讲得不是很详细，求修正

[oujunsong]

“筛法求约数个数”和“筛法求约数和”讲得不是很详细，希望能像“ 筛法求欧拉函数 ”那样分类讨论说详细点

[QifanWang]

筛法求莫比乌斯函数那一节公式应该是
n' mod p1 = 0

[HowieHz]

@zmxqs
那个埃拉托斯特尼筛法有问题。

int j=i*i

你确定是ii？筛倍数应该是2i才对啊

一开始也没看懂

后面想到，(i-1)的倍数都筛过了，所以就不用再筛一次了

[cubeheadsun]

我觉得那个线性筛的注释有问题

[alexandrelea]

问个问题，Eratosthenes 可否这样做：

const int range=1e6;
bool isprime[range+10];
void eratosthenes(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=2;i*i<=range;i++){
        if(isprime[i]) for(int j=2;j*i<=range;j++) isprime[i*j]=false;
    }
    return;
}

使时间复杂度达到 $\mathrm O(\ln(\ln n)\sqrt{n})$

[Tiphereth-A]

这个还是 $O(n\log\log n)$ 吧 🤔

[Tyruetrue]

$oiwiki$ 的欧拉筛求欧拉函数我感觉是全网最好懂的，可能是因为先证明了结论，再进行扩展，比较牛

[demeter1210]

蒟蒻表示很抽象

[mahaoming2022]

好，理解。

[demeter1210]

orz，拜谢

…

________________________________ 发件人: FIRESTARS-ZFYX ***@***.***> 发送时间: 2024年8月28日 16:48 收件人: OI-wiki/gitment ***@***.***> 抄送: demeter1210 ***@***.***>; Comment ***@***.***> 主题: Re: [OI-wiki/gitment] 筛法 (Discussion #647) %%% ― Reply to this email directly, view it on GitHub<#647 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BIYBOA7SEFD7UGR2S5XV3ITZTWFF3AVCNFSM6AAAAAATJQCYAKVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTANBXGI2DMMI>. You are receiving this because you commented.Message ID: ***@***.***>