区间筛：类似于埃式筛法
【分析】b以内的合数的最小质因数一定不超过sqrt(b)。如果有sqrt(b)以内的素数表的话，就可以把埃式筛法运用在[a,b)上了。也就是说，先分别做好[2,sqrt(b))的表和[a,b)的表，然后从[2,sqrt(b))的表中筛得素数的同时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了。
给定整数 a 和 b，请问区间 [a,b) 内有多少个素数？（a<b≤1012,b−a≤106）
因为 b 以内合数的最小质因数一定不会超过 √b，因为如果存在 d 是 n 的约数，那么 n/d 也是 n 的约数，由 n=d×n/d 可知 min(d,n/d)≤√n
如果有 √n 以内的素数表的话，就可以把埃式筛法用在 [a,b) 上了。也就是说，先分别做好 [2,√b) 的表和 [a,b) 的表，然后从 [2,√b) 的表中筛得素数的同时，也将其倍数从 [a,b) 的表中筛去，最后剩下的就是区间 [a,b) 内的素数了
假如要求 [1e9,1e9+2) 区间内的素数，难道我们要开 1e9+3 大小的数组吗？其实并不用，我们利用下标偏移，可以减少空间开销。即将 [1e9,1e9+2) 对应到[0,2)，整体区间向左偏移 1e9
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 1e5; bool is_prime[MAXN]; bool is_prime_small[MAXN]; ll prime[MAXN]; ll prime_num = 0; //对区间[a,b)内的整数执行筛法，is_prime[i-a]=true <=> 表示i是素数（下标偏移了a） void segment_sieve(ll a, ll b) { for (ll i = 0; i * i < b; i++) //对[2,sqrt(b))的初始化全为质数 is_prime_small[i] = true; for (ll i = 0; i < b - a; i++) //对下标偏移后的[a,b)进行初始化 is_prime[i] = true; for (ll i = 2; i * i < b; i++) { //筛选[2,sqrt(b)) if (is_prime_small[i]) { for (ll j = 2 * i; j * j < b; j += i) is_prime_small[j] = false; //(a+i-1)/i 得到最接近a的i的倍数，最低是i的2倍，然后筛选 for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) is_prime[j - a] = false; } } for (ll i = 0; i < b - a; i++) //统计个数 if (is_prime[i]) prime[prime_num++] = i + a; } int main() { ll a, b; while (~scanf("%lld%lld", &a, &b)) { prime_num = 0; memset(prime, 0, sizeof(prime)); segment_sieve(a, b); printf("%lld\n", prime_num); } return 0; }
例一：
给定整数a和b，请问区间[a,b)内有多少个素数？
a< b<=10^12
b-a<=10^6
输入
22 37
输出
3
输入
22801763489 2280178297
输出
1000
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<vector> #include<queue> #include<stack> using namespace std; #define LL long long #define MAX_L 1000007 #define MAX_SORT_B 1000007 bool is_prime[MAX_L]; bool is_prime_small[MAX_SORT_B]; //对区间[a,b)内的整数执行筛法。isprime[i - a]=true <=> i是素数 void segment_sieve(LL a,LL b) { for(int i=0; (LL)i*i < b; i++)is_prime_small[i]=true; for(int i=0; i<b-a; i++)is_prime[i]=true; for(int i=2; (LL)i * i<b; i++) { if(is_prime_small[i]) { for(int j=2*i; (LL)j * j < b; j += i) { is_prime_small[j]=false;//筛[2,sqrt(b)) } for(LL j=max(2LL, (a+i-1)/i)*i ; j<b; j+=i) //(a+i-1)/i为[a,b)区间内的第一个数至少为i的多少倍. { is_prime[j - a] =false;//筛[a,b) } } } } int main() { long long a,b; while(~scanf("%lld %lld",&a,&b)) { segment_sieve(a,b); int cnt=0; for(int j=0; j<b-a; j++) { if(is_prime[j])cnt++; } if(a==1)cnt--; printf("%d\n",cnt); } return 0; }
例二：
Prime Distance
http://poj.org/problem?id=2689
数学的一个分支叫做数论，它是关于数字的性质的。千百年来，数论家们感兴趣的领域之一就是质数问题。质数是一个没有适当因数的数(它只能被1和它本身整除)。第一个质数是2 3 5 7但它们很快就变得不那么频繁了。一个有趣的问题是它们在不同范围内的密度。相邻质数是两个都是质数的数，但是相邻质数之间没有其他质数。例如，2,3是唯一的相邻质数也是相邻数。
你的程序有两个数字:L和U (1<=L<U<=2,147,483,647)，你要找到两个相邻的素数C1和C2 (L<=C1<C2<=U)，它们是最接近的(即C2-C1是最小的)。如果有其他的一对距离相同，就用第一对。你还需要找出两个相邻的素数D1和D2 (L<=D1< D2<=U)其中D1和D2的距离越远越好(如果有平手，同样选择第一对)。
输入
输入的每一行都包含两个正整数，L和U，并且L < U。L和U之间的差值不会超过1,000,000。
输出
对于每一个L和U，其输出要么是不存在相邻素数(因为两个给定的数之间小于两个素数)，要么是一条给出两对相邻素数的直线。
Sample Input
2 17 14 17
Sample Output
2,3 are closest, 7,11 are most distant. There are no adjacent primes.
解析：
问题就是说在一个大区间中求相邻素数的最大最小值，
#include<iostream> #include<algorithm> #include<map> #include <math.h> #include<memory.h> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } const int maxn=1e6+100; const ll mod=1e9+7; ll prime[maxn];//储存素数 ll biaoji[maxn]={0}; ll cnt=0; ll dabiao[maxn]; ll prime2[maxn];//大标记素数 void primem(){ for(int i=2;i<maxn;i++){ if(!biaoji[i]){ prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){ biaoji[i*prime[j]]=1; if(i%prime[j]==0){ break; } } } } ll p=0; void qujianshai(ll l,ll r){ p=0; memset(dabiao,0,sizeof(dabiao)); for(ll i=1;i<=cnt&&prime[i]*prime[i]<=r;i++){ for(ll j=max(2LL,(l+prime[i]-1)/prime[i])*prime[i];j<=r;j+=prime[i]){ if(j>=l){ dabiao[j-l]=1; } } // ll x=l/prime[i]+(l%prime[i]>0); // if(x==1) x=2; // for(int j=x;j*prime[i]<=r;j++){ // if(j*prime[i]>=l){ // dabiao[j*prime[i]-l]=1; // } // } } for(int i=0;i<=r-l;i++){ if(dabiao[i]==0){ if((i+l)!=1) prime2[++p]=i+l; } } } int main(){ primem(); ll l,r,n,m; while(~scanf("%lld%lld",&l,&r)){ if(l==1) l=2; qujianshai(l,r); if(p<2){ printf("There are no adjacent primes.\n"); } else{ ll ma=0,mi=20*mod; ll x,y,a,b; for(int i=1;i<p;i++){ if(prime2[i+1]-prime2[i]>ma){ ma=prime2[i+1]-prime2[i]; x=prime2[i],y=prime2[i+1]; } if(prime2[i+1]-prime2[i]<mi){ mi=prime2[i+1]-prime2[i]; a=prime2[i],b=prime2[i+1]; } } printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a,b,x,y); } } return 0; }
原文：https://www.cnblogs.com/lipu123/p/12405132.html