双重素数（2021 CoE-II A）

· · 题解

1 理解题意

首先读题(看这里)

找出文中重要信息：

2 分析题目

思路：

  1. 定义一个变更的左(L) 右(R) 区间来节省第二次筛查时间与空间

  2. 第一遍筛出普通的素数

  3. 第二遍重复利用，再筛出题目所要求的双重素数

分析：看一眼数据：1≤L≤R≤10^8，数据较大，要用适当方式来卡常

这时候就要用到 lower_bound 和 uppere_bound 了

Tips：

lower_bound() 和 upper_bound() 都是C++自带的函数，利用二分查找

在一个排好序的数组中进行区间查找最小值及最大值的函数

声明方式: lower_bound(begin,end,num)

解释：

从数组的 begin 位置到 (end-1) 位置二分查找第一个大于等于 num 的数字

找到返回该数字的地址，不存在则返回 end

通过返回的地址减去起始地址 begin，得到找到数字在数组中的下标

(upper_bound 与之相反，不在此赘述)

3 代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()//快读+快速查找
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    }
    return s*f;
}
const int N=6e6+5,M=1e8+10;
int prime[N],pm,kl;//prime 用来存第一遍筛出来的素数 
bitset<M> vis;
inline bool check(int x)//更新筛后素数的位置，方便第二次筛选
{
    int ret=0;
    while(x)
    {
        ret+=x%10;x/=10;
    }
    return !vis[ret];
}
inline void init(int n)//筛素数(第二次也是用这个，重复使用)
{
    for(int i=2;i<=n;++i)
    {
        if(!vis[i])
        {
            prime[++pm]=i;
        }
        for(int j=1;j<=pm&&1ll*prime[j]*i<=n;++j)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                break;
            }
        }
    }
    for(int i=1;i<=pm;++i)
    {
        if(check(prime[i]))//更新prime数组 
            {
                prime[++kl]=prime[i];
            }
    }
}
struct lxz{//定义结构体来确定左右区间
    int L,R;
}q[105];
int T,mx;
int main()
{
    T=read();
    for(int i=1;i<=T;++i)
    {
        q[i].L=read();q[i].R=read(); 
        mx=max(mx,q[i].R);
    }
    init(mx);
    for(int i=1,p1,p2;i<=T;++i)
    {
        p2=lower_bound(prime+1,prime+kl+1,q[i].R+1)-prime;//lower_bound节省时间
        p1=lower_bound(prime+1,prime+kl+1,q[i].L)-prime;
        printf("%d\n",p2-p1);
    }
    return 0;
}

在我的博客中查看