筛素数，求区间内素数个数-白红宇的个人博客

筛素数，求区间内素数个数

发布日期：2021-05-14 16:48:53 浏览次数：19 分类：精选文章

本文共 733 字，大约阅读时间需要 2 分钟。

问题 1525: [蓝桥杯][算法提高VIP]找素数

时间限制: 1Sec 内存限制: 128MB 提交: 1179 解决: 133

题目描述

给定区间[L, R] ，请计算区间中素数的个数。

数据规模和约定

2 < = L < = R < = 2147483647 R-L < = 1000000

输入

两个数L和R。

输出

一行，区间中素数的个数。

样例输入

2 11

样例输出

解题报告：用sqrt（r）以内的数筛掉r以内的所有合数，因为区间小于等于1e6开这么大的数组就够了，数组下标记录的是这个数和l的相对差。注意该题的大优化。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int N=1000010;bool f[N];bool t[N];void init(ll l, ll r){ for(ll i=2;i*i<=r;i++) { if(!f[i]) { for(ll j=2*i;j*j<=r;j+=i) f[j]=1; ll j=2*i; if(j
            
             >l>>r; init(l,r+10); ll cnt=0; for(ll i=l;i<=r;i++) if(!t[i-l]) cnt++; cout<
             
              <

上一篇：问题 1529: [蓝桥杯][算法提高VIP]摆花

下一篇：蓝桥训练-拓扑排序

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章