UVA10140PrimeDistance题解--质数/技巧

题目链接

https://www.luogu.org/problemnew/show/UVA10140

分析

$L,R$都很大,显然不能直接筛出$L,R$区间中的质数,这里需要一个结论

结论

任何一个合数$N$必定含有一个小于等于$\sqrt N$的质因子

证明

反证法,若所有质因子都大于$\sqrt N$,那么无论怎么组合显然都大于$N$

于是通过这个结论筛出$[2,\sqrt R]$,中的所有素数,把它们看作质因子筛出$[L,R]$中的所有合数

注意如果$L$为$1$的话需要注意,不要把$1$标记为质数,对拍了好久才发现…真坑啊

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <cmath>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=1500005;
const int inf=0x7fffffff;
int l,r;
bool ok[maxn],vis[50000];
int prime[50000],tot=0;
inline void get_prime(){
	int lim=(int)(std::sqrt(1.0*inf+0.5));
	//printf("%d\n",lim);
	for(ri i=2;i<=lim;i++){
		if(!vis[i]){
			vis[i]=1;
			prime[++tot]=i;		
		}
		for(ri j=1;j<=tot&&1ll*prime[j]*i<=lim;j++){
			vis[i*prime[j]]=1;	
			if(i%prime[j]==0)break;
		}
	}
	return ;
}
inline void solve(int n){
	int lim=(int)(std::sqrt(1.0*n+0.5));
	memset(ok,0,sizeof(ok));
	int o=1;
	while(prime[o]<=lim&&o<=tot){
		for(ri k=l/prime[o];k<=r/prime[o];k++){
			if(k==1||k==0)continue;
      /*注意k=1及k=0都是不合法的情况*/
			ok[k*prime[o]-l]=1;
      /*左移L位以储存结果*/
		}
		o++;
	}
	return ;
}
int main(){
	freopen("dat.in","r",stdin);
	freopen("wa.out","w",stdout);
	get_prime();
	while(scanf("%d %d",&l,&r)!=EOF){	
	    /*注意!!!*/	
		if(l==1)l=2;                
		//注意!!! 1不是质数 
		int lnum,lst=-inf,xans=-1,ians=inf; 
		int a,b,c,d;
		solve(r);
		for(ri i=0;i<=r-l;i++){
			if(!ok[i]){
				if(lst!=-inf){
					//xans=max(xans,i-lst);
					if(i-lst>xans){
						c=lst,d=i;
						xans=i-lst;
					}
					if(i-lst<ians){
						a=lst,b=i;
						ians=i-lst;
					}
					//ians=min(ians,i-lst);
				}
				lst=i;
			}
		}
		if(xans==-1){
			puts("There are no adjacent primes.");
 		}
		else{
			printf("%d,%d are closest, %d,%d are most distant.\n",a+l,b+l,c+l,d+l);
		}
	}
	return 0;
}