试除法和埃氏筛欧拉筛等素数筛法时间差的很多吗 - acm吧

level 5

home友谊第一楼主

2022年03月19日 06点03分 1

level 13

试除法单个数判断就要O(sqrt(n))，筛法对区间内判断更占优。具体见https://oi-wiki.org/math/number-theory/sieve/(oi-wiki点org/math/number-theory/sieve/)

2022年03月19日 17点03分 2

我是在考虑sqrt(n) 累加和 nlogn 的大小另外请问一下大佬欧拉筛的O(n)总会优于埃氏筛吗 [吐舌]

2022年03月19日 18点03分

爬爬怪

@home友谊第一累加就是比较nsqrt(n)和nlogn，sqrt在n＞0比log大，欧拉筛是埃氏筛的优化，但是你问有没有可能埃氏筛更优，那还要根据n的大小和两个算法实现的常数进行比较。不过再优也不会超过一个数量级，欧拉筛也不难实现，所以没必要为了这点时间考虑用哪个

2022年03月19日 19点03分

@爬爬怪是我太较真了我当时想试除法时间复杂度∑i(1,n)sqrt(i) 可能没必要扣这么细也是效率怎么样都不行没必要这样较真 [吐舌]

2022年03月20日 09点03分

level 1

如果没记错的话，1e5以内的数据这三种差别不大，1e6的话nlgn和n差别不大，1e7开始的话n在时间上远低于另外两个

2022年05月07日 22点05分 3

额这个1e7本身也是要超的节奏啊 [泪]

2022年05月07日 23点05分

@home友谊第一如果是线性筛的话可以开到1e8往上，具体多少看评测机性能了

2022年05月07日 23点05分