【洛谷P1835】素数密度
2024-10-01 11:35:19
题目描述：
给定区间[L，R](L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。
思路：
暴力：
蒟蒻：哦？绿题？这么水？（便打出下面代码）
这绝对是最容易想到的！但，时间复杂度\(O(n \cdot\) \(\sqrt{n}\) $ )$
恭喜蒟蒻获得\(\color{red}\texttt{0分}\)
正解：
思考：
怎么样的数是素数？
回答：
（由小学知识可得） 素数是除自己和\(1\)以外,没有其他约数
埃氏筛法：
埃氏筛法的优化是在于它用素数筛掉合数，不用因合数运算多次。
其实这道题也是这样的，看上去\(L\)和\(R\)很大，但是你只需要用一个个素数筛掉合数就行了，因为\(R-L≤10^6\)。
思考:
那我们又不知道\(L\sim R\)里素数的多少，这么筛？
回答：
就拿\(2147483647\)的极限数据来说吧！
照蒟蒻 【我】 的程序和刚刚说的来看，你只用把\(2 \sim \sqrt{2147483647}\) 里的素数去筛就可以了。
代码：
最新文章
- session过期，登录页被内嵌iframe的解决方案
- 备忘：hibernate, logback, slf4j实际应用一例
- 集成ShareSDK里报错NSConcreteMutableData wbsdk_base64EncodedString]
- [IBM DB2] db2 terminate 和 db2 connect reset 有什么区别?
- J2msi 自己制作的把exe打成安装包简易GUI程序(第二版 带DLL注册)
- centos linux
- php删除数组中相同的元素，只保留一个相同元素
- C++ 我想这样用（二）
- Apache与php的整合（经典版），花了一天去配置成功经验
- How Node.js Multiprocess Load Balancing Works
- "创业"半年
- hdu 5073 Galaxy（2014acm鞍山亚洲分部 C）
- [bzoj 1409] Password 矩阵快速幂+欧拉函数
- js中的Object.defineProperty()和defineProperties()详解
- SpringBoot工作机制
- Python算法和数据结构：在二叉树中找到和为sum的所有路径
- 性能之ab简单使用
- [SimplePlayer] 1. 从视频文件中提取图像
- nagios nrpe
- VS下.net开发常用扩展、配置