当前位置:首页 > 数学 > 筛法 > 正文
洛谷P1835素数密度[NOI导刊]
59+

题目大意:区间[L, R]中有多少个质数?区间大小不超过100万,L、R在int范围。

题目描述

给定区间 $[L,R]$($1\leq L\leq R < 2^{31}$,$R-L\leq 10^6$),请计算区间中素数的个数。

输入输出格式

输入格式

第一行,两个正整数 $L$ 和 $R$。

输出格式

一行,一个整数,表示区间中素数的个数。

输入输出样例

输入样例 #1

2 11

输出样例 #1

5

解题思路

一个合数n,总会有一个质因子,不超过$\sqrt{n}$,我们可以筛出int开根号内的所有质数,然后用他们去筛合数,剩下的就是质数。

虽然区间[L, R]很大,但L之前和R之后都不需要筛,如L=100000,R=500000,质数2如果从4开始筛,那么4~99998都是白做的,我们可以从L/2倍开始,每次增加2,这样每个质数p只需要循环(R-L)/p次即可,时间复杂度就是O(nlogn)。

注意,质数翻倍过程中,需要筛的是[L, R]内的,0倍和1倍需要过滤掉。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

洛谷P1835素数密度[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter