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

问题描述

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

输入格式

　　两个数L和R。

输出格式

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

样例输入

2 11

样例输出

5

数据规模和约定

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

 

核心代码：for(ll j = max(2LL, (a+i-1)/i) *i; j <=b; j += i)

（这里主要考虑a和i的关系，b仅仅是一个界限） 假如i=2，a=2， 那么第一个离a最近（必须大于等于a）的非素数为4；（注意这个比较特别） 假如i=2，a=3， 那么第一个离a最近（必须大于等于a）的非素数为4； 假如i=2，a=4， 那么第一个离a最近（必须大于等于a）的非素数为4； 假如i=2，a=5， 那么第一个离a最近（必须大于等于a）的非素数为6； 假如i=2，a=6， 那么第一个离a最近（必须大于等于a）的非素数为6； 假如i=2，a=7， 那么第一个离a最近（必须大于等于a）的非素数为8； 假如i=2，a=8， 那么第一个离a最近（必须大于等于a）的非素数为8； 如果a 可见，对于a<2i时，数据没有按照规律发展，独立列举，当a>2i时，才有规律，第一个离a近距离的数为(a+i-1)/i) 倍的i（找规律即可）。 转自某dalao。。

#include 
   
    using namespace std;typedef long long ll;const int MAXN=9999999;int sum=0;bool is_prime[MAXN], vis[MAXN];void getprime(ll a, ll b){    memset(vis, true, sizeof(vis));    for(int i = 0; i < b - a+1; i++)        is_prime[i] = true;    for(int i = 2; (ll)i * i <=b; i++)	{        if(vis[i])		{            for(int j = 2*i; (ll)j*j <=b; j += i)				vis[j] = false;            for(ll j=max(2LL,(a+i-1)/i) *i; j <=b; j += i)			{                is_prime[j-a]=false;            }        }    }}int main(){    ll a, b;    ios::sync_with_stdio(false);    cin>>a>>b;    getprime(a,b);    for(ll i = a; i <= b; i++)    {        if(is_prime[i-a])        sum++;    }    cout<
    
     <
    
   

 

转载地址：http://ixyzi.baihongyu.com/