196. 质数距离

196. 质数距离

题目链接：https://www.acwing.com/problem/content/198/?time=1562239536766

题目描述：

给定两个整数L和U，你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数L和U，其中L和U的差值不会超过1000000。

输出格式

对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。

数据范围

1≤L<U≤231−11≤L<U≤231−1

输入样例：

2 17

14 17

输出样例：

2,3 are closest, 7,11 are most distant.

There are no adjacent primes.

思路：

首先我们发现：R−L 的范围很小，我们应该要能够快速求出 L∼sqrt(R)之间的质数。

显然有推论：任意一个合数 x 必定包含一个不超过 sqrt( x)的质因子。

所以我们可以筛出 [1, sqrt(R) ] 之间的所有质数，对于每个质数 p，把 [L,R] 中能被 p 整除的数标记为合数。最终没有被标记的数就是质数，对相邻的质数两两比较，找出差值最小和最大的即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 100003

#define maxn 1000005

#define INF 0x3f3f3f3f

int v[maxn], prime[maxn];

int shu[maxn];

int result[maxn];

int m = 0;

void xianxing(int n)//线性筛法

{

    for (int i = 2; i <= n; i++)

    {

         if (v[i] == 0)

         {

             v[i] = i;

             prime[++m] = i;

         }

         for (int j = 1; j <= m; j++)

         {

             if (prime[j] > v[i] || prime[j] * i > n)

             {

                  break;

             }

             v[i*prime[j]] = prime[j];

         }

    }

    /*for (int i = 1; i <= m; i++)

    {

         cout << prime[i] << " ";

    }*/

}

int main()

{

    int r, l;

    xianxing(46340);

    while (cin >> l >> r)

    {

         memset(shu, 0, sizeof(shu));

         for (int i = 1; i <= m; i++)//把 l到r 的所有的质数的倍数必为合数，数组里标记为1

         {

             //if (prime[i] > r / 2)break;

             for (int j = l / prime[i]; j <= r / prime[i]; j++)

             {

                  //cout << j << endl;

                  while (j <= 1)j++;

                  if (prime[i] * j<l || prime[i] * j>r)continue;

                  //cout << j * prime[i] << " ";

                  shu[j*prime[i] - l] = 1;//数组平移

             }

         }

         //cout << "aAAAA" << endl;

        if (l == 1)shu[0] = 1;

         int num = 0;

         for (int i = 0; i <= r - l; i++)

         {

             if (!shu[i])

             {

                  //cout << i + l << " ";

                  result[++num] = i + l;//复制到另一个数组里面去，这样好比较

             }

         }

         int maxx = 0;

         int minn = INF;

         int a1, a2, b1, b2;

         for (int i = 1; i < num; i++)//一个个相邻的质数去比较，算出他的最大值和最小值

         {

             if (maxx < result[i + 1] - result[i])

             {

                  maxx = result[i + 1] - result[i];

                  a1 = result[i];

                  a2 = result[i + 1];

             }

             if (minn > result[i + 1] - result[i])

             {

                  minn = result[i + 1] - result[i];

                  b1 = result[i];

                  b2 = result[i + 1];

             }

         }

         //cout << maxx <<" " <<minn << endl;



         if (maxx == 0 && minn == INF)

         {

             cout << "There are no adjacent primes." << endl;

         }

         else

         {

             cout << b1 << "," << b2 << " are closest, " << a1 << "," << a2 << " are most distant." << endl;

         }

         //cout << a1 << " " << a2 << " " << b1 << "  " << b2 << endl;

    }

}