首页 > 素数的个数
开通博客写题解
头像 重生之我是大菜狗
发表于 2023-07-05 13:38:28
R-L<=10的6次方，则开一个10的6次方的数组，对于每一个素数都减去L存入数组，1~20亿中大概有近一亿个素数，用欧拉筛也不可能完成，所以只能在L,R区间内判断，一个一个求明显会TLE。 所以转换思路，利用两层循环i*j来求出L,R内有质因子的数，乘出来的数一定是质数，直接排除。 展开全文
去ta的博客 赞 (12) 回复(0) 收起
头像 Zhao05
发表于 2025-07-08 16:45:30
首先,筛法一定不行,数组会爆掉 筛法+前缀和版本可以去看洛谷P1865 那么本题要怎么做? 答案:MR素性判断 MR算法可以在k*(logn)^2时间复杂度内判断一个数是不是质数 只需要在l到r区间的i进行MR判断就行了 第一次写题解,而且MR算法 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”