P1835 素数密度

根据引用\[1\]和引用\[2\]的内容，题目P1835要求统计一个范围内的素数个数。这个范围可以在int的任意范围内，但区间的大小小于1000000。为了解决这个问题，可以使用线性筛法来预处理素数列表，并用这些质因数标记\[L,R\]范围内的合数。

首先，使用线性筛法来预处理素数列表。具体步骤如下：
1. 初始化isprime数组，将所有元素标记为1，表示都是素数。
2. 从2开始遍历到50000，如果isprime\[i\]为1，则将i加入prime数组，并将isprime\[i\]标记为0。
3. 对于每个素数prime\[i\]，从1开始遍历到now，并且i*prime\[j\]小于50000，将isprime\[i*prime\[j\]\]标记为0。如果i能整除prime\[j\]，则跳出内层循环。

接下来，使用res数组来标记\[L,R\]范围内的合数。具体步骤如下：
1. 初始化res数组，将所有元素标记为1，表示都是素数。
2. 对于每个素数prime\[i\]，从max(2,(l-1)/prime\[i\]+1)开始遍历到r，将res\[j*prime\[i\]-l\]标记为0。这里的j至少为2才有意义，否则j=0或者1的时候会出错。同时，要注意(long)j*prime\[i\]<=r，因为如果都是int会溢出。
3. 如果l<=1，将res\[1-l\]标记为0。
4. 遍历res数组，统计标记为1的个数，即为素数的个数。

根据以上步骤，可以得到解决题目P1835的代码。
#### 引用[.reference_title]
- *1* *2* [【洛谷】P1835 素数密度](https://blog.csdn.net/u014156276/article/details/108294974)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]