洛谷题单指南-数学基础问题-P1835 素数密度

原题链接：https://www.luogu.com.cn/problem/P1835

题意解读：要计算L-R范围内素数的个数。

解题思路：

直接对L~R的每个数判断素数肯定不可取，因为L、R的范围较大。

既然要计算素数的个数，那么可以把其中的合数标记出来即可。

如何标记合数？

可以借助于筛素数的算法思想，枚举每一个素数，然后把素数的2/3/4....n倍，且乘以倍数后在L~R范围内的数标记成合数，最后计算素数的个数即可。

问题在于，枚举每一个素数，这个最大的素数到多少合适？会不会超时？

如果合数最大是x，那么素数最多只要枚举到sqrt(x)，就可以把所有合数都标记到。

因此，我们要枚举的素数最大在10^5内即可，放大一点，我们可以先筛出10^6范围内的所有素数，再枚举倍数，标记L~R范围内的合数。

枚举倍数从多少开始，到多少结束呢？

给定一个素数primes[i]，倍数j起始点肯定是j * primes[i]接近l，倍数j的结束点肯定是j * primes[i]解决r，这样枚举次数最少

因此起点start = l / primes[i]，终点end = r / primes[i]即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int primes[N], cnt;
bool flag[N];
int l, r, c;
int h[N]; //标记出l~r之间的合数

int main()
{
    cin >> l >> r;
    if(l == 1) l++; //排除1的影响

    //筛2~1000000质数
    for(int i = 2; i <= 1000000; i++)
    {
        if(!flag[i])
        {
            primes[++cnt] = i;
            for(int j = i + i; j <= 1000000; j += i)
            {
                flag[j] = true;
            }
        }
    }

    for(int i = 1; i <= cnt; i++) //枚举每一个素数，再枚举倍数，使得素数*倍数在l~r范围内，则标记为合数
    {
        int start = l / primes[i]; //筛出l-r范围内的合数，也就是素数的倍数从l/primes[i]开始
        int end = r / primes[i]; //倍数到r/primes[i]截止
        if(start <= 1) start = 2; //起始至少从2倍开始
        if(end <= 1) break; //如果截止倍数不到2倍，则不可能筛出合数，后面的素数更大，end更小，提前退出
        for(int j = start; j <= end; j++)
        { 
            if(j * primes[i] >= l)
            {
                h[j * primes[i] - l] = 1; //标记l~r之间的合数，-l防止溢出
            } 
        }
    }
    
    int ans = r - l + 1;
    for(int i = 0; i <= r - l; i++)
    {
        if(h[i]) ans--;
    }
    cout << ans;

    return 0;
}