题目描述
196. 质数距离 - AcWing题库
样例
输入：
输出:
1
2
| 2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
|
算法
$$
如果是暴力的线性筛找一遍 2^{31}显然是不可取的，线性筛肯定会超时。l和r之间最多差10^{6}，那用试除法的话，
$$
$$
跑满复杂度也大概再10^{10}，那肯定也是会超时的。因此应该换一个思路，总所周知筛质素是去掉里面的合数剩下
$$
剩下的就是质数。我们也可以用同样的方法去掉l和r之间的所有的合数，然后就能得到所有的质数。
$$
一个合数x，它最小的质因子是小于等于\sqrt(x),因此我们只需要筛出1~\sqrt(r)的质数，然后再用再去掉是这些质
$$
因子的倍数的数即可。
求质数p大于等于x最小倍数公式：
$$
num=(x+p-1)/p;//下取整 \\n
num=x/p;//上取整
$$
1
2
3
4
5
6
| for(int i=1; i<=cnt&&primes[i]<=r; i++){//primes[i]是已经筛出来的的质因子
int p=primes[i];
for(int j=max(p*2,(l+p-1)/p*p); j<=r; j+=p){//解释一下为什么是max(p*2,(l+p-1)/p),如果j等小于2*p也就是j等于p那j就是个质数所以我们不能给它做标记
st[j-l+1]=true;//把是这些质因子的倍数去掉
}
}
|
上述代码中的j-l+1是处理把它压缩大于等于l的第几个数，这样可以节省空间再1e6内
也就是我们存的每个素数它都要减去L加1；
处理完之后暴力找答案就可以了
C++ 代码
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int primes[1000000],cnt;
bool st[1100000];
void init(int k)
{
cnt=0;
for(int i=2; i<=k; i++)
{
if(!st[i])primes[++cnt]=i;
for(int j=1; j<=cnt&&i*primes[j]<=k; j++)
{
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
signed main()
{
int l,r;
while(cin>>l>>r)
{
memset(st,0,sizeof st);
init(1000000);
memset(st,0,sizeof st);
if(l==1)st[1]=1;
for(int i=1; i<=cnt&&primes[i]<=r; i++)
{
int p=primes[i];
for(int j=max(p*2,(l+p-1)/p*p); j<=r; j+=p)
{
st[j-l+1]=true;
}
}
cnt=0;
for(int i=1; i<=r-l+1; i++)
if(!st[i])primes[++cnt]=i;
if(cnt<=1) puts("There are no adjacent primes.");
else
{
int mi=9999999999,ma=0,di=0,da=0;
for(int i=2; i<=cnt; i++)
{
if(primes[i]-primes[i-1]>ma)
{
da=i;
ma=primes[i]-primes[i-1];
}
if(primes[i]-primes[i-1]<mi)
{
di=i;
mi=primes[i]-primes[i-1];
}
}
printf("%d,%d are closest, %d,%d are most distant.\n",primes[di-1]+l-1,primes[di]+l-1,primes[da-1]+l-1,primes[da]+l-1);
}
}
}
|
所以呢就别不快乐。