196. 质数距离 (筛素数,离散化)

196. 质数距离 (筛素数,离散化)

196. 质数距离 - AcWing题库 

这里参考于大佬的题解:AcWing 196. 质数距离 - AcWing

前言:由于L,U最大可以取到2^32-1,2^31-1是约等于2e9,如果采用普通的线性筛法的话,无论是时间复杂度还是空间复杂度都是O(n)==O(2e9),那必然是会超时的,那么我们就思考一下怎么做出优化。

分析:由于注意到 L,U 的差值只是1e6,那么采用O(n)或者O(nlogn)的做法

总结一下y总的思路,如下

  • 一个合数n的两个因子,必然有一个不会超过sqrt(n),那么sqrt(2^31)≈50000,可以在时间复杂度接受的范围之中
  • 如果n是合数,那么一定存在在(1~50000)中间有一个因子P,(1<P<n)

步骤

  • 首先筛选出1~50000内所有的质数
  • 运用埃氏筛质数法,1~50000内所有的质数P在[L,R]中的倍数都被染色成为合数,剩下没有被染色的就是质数

埃氏筛质数法:保证一个数只会被他的质因子染色,也就是说用质因子去染色在[L,R]范围内的所有倍数,首先为了避免不必要的操作,需要先计算出在(L,R)范围内,关于质因子p的最小倍数,

也就是L/p (上取整),等价于 L+p-1/p (下取整)。那么在埃氏筛法里面,模板如下

for (int i = 0;i < cnt;i++)
{
      int P0 = primes[i];//至少是2倍,不然质数本身会被染色,或者[L/p]倍,所以取最大值
      for (ll j = max(0ll + 2 * P0, (l + P0 - 1) / P0*P0);j <= u;j += P0)
      {//离散化的步骤,用j-l离散化
            st[j - l] = true;   //表示j是一个合数          
      }
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
bool st[N];
int primes[N];
int cnt;
int mp[N];
ll ans[N];
void print()
{
    cout << 1 << ' ';
    exit(0);
}
void solve(int n)
{//欧拉筛法
    cnt = 0;memset(st, 0, sizeof st);
    for (int i = 2;i <= n;i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0;primes[j] <= n / i;j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int main()
{
    ll l, u;
    while (cin >> l >> u)
    {
        memset(ans, 0, sizeof ans);
        solve(50000);
        memset(st, 0, sizeof st);
        for (int i = 0;i < cnt;i++)
        {
            int P0 = primes[i];
            for (ll j = max(0ll + 2 * P0, (l + P0 - 1) / P0*P0);j <= u;j += P0)
            {
                st[j - l] = true;   //表示j是一个合数          
            }
        }
        cnt = 0;
        for (int i = 0;i <= u - l;i++)
        {   //由于2不是一个质数,所以要特判一下
            if (!st[i]&&i+l>=2) ans[cnt++] = i + l;
        }
        int maxx = 0, minn = 0;
        for(int i=0;i+1<cnt;i++)
        {
            int d=ans[i+1]-ans[i];
            if(ans[maxx+1]-ans[maxx]<d) maxx=i;
            if(ans[minn+1]-ans[minn]>d) minn=i;
        }
        if(cnt<2) printf("There are no adjacent primes.\n");
        else
        {
            printf("%d,%d are closest, %d,%d are most distant.\n",ans[minn],ans[minn+1],ans[maxx],ans[maxx+1]);
        }
    }
    return 0;
}

上一篇:项目中常用的D3D黑屏优化讲解和源码分享,DX系列的游戏都可以用


下一篇:acwing 196