蓝桥杯第十三届蓝桥杯大赛软件赛决赛CC++ 研究生组之选素数

蓝桥杯第十三届蓝桥杯大赛软件赛决赛C/C++ 研究生组之选素数

[题目传送门](0选素数 - 蓝桥云课 (lanqiao.cn))

问题大意：

小蓝有一个数字，要进行如下操作：

首先选出一个小于x 的质数p，然后将x变成要比原本大的最小的为p的倍数的x1。

听上去有点绕，举个例子说明一下：

比如取x值为6，比6小的素数有2，3，5

则当取的素数为2时，x为6保持不变，因为6为2的倍数。

当取的素数为3时，x为6保持不变，理由同上。

当取的素数为5时，则x最大可以变为10.

进行一次操作时

而如今的题意是反过来的，在上述中是知道了x，然后可以知道最大为x1.

现在是知道了x1，要知道其最小的x是多少。

比如知道了现如今的x1为10，最小的x可以取值为多少？

其方法就是求x1的最大质因数，其最大质因数+1即为所求。

设所求的值为x，现如今知道x1的最大质因数为p,则x=x1-p+1

还是以上述为例

现如今知道的x1为10，其最大的质因数为5,因而其要求的x是10-5+1=6.

现如今的题意是进行两次这样的操作：

设要求的值为x,进行一次这样的操作后的值为x1,进行第二次这样的操作后的值为x2.

例:

第一次：

x2=22, 22最大的质因数为11，则在此区间中可以取得值为 12–22，其中的素数如13、15可以忽略，因为素数的最大质因数就是其本身。

求解时候搜索这个区间内，满足条件的最小值x即可。此时12–22这个所取得值的意思是指，第一步时候的x1。

设f（i）表示i最大的质因数，则最终答案的x=i-f(i)+1

如当i=14时，其最大质因数为7，则x=8，此时值为最小的。12–22之间的其他数，也可以试一下，f(14)=7。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6 + 10;
bool judge_su(int n) //判断是不是素数
{
    if(n==2)
    {
        return true;
    }
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
int get_max_prime(int n,vector<bool>& is_prime) //获得n最大的质因数
{
    for(int j=n;j>=2;j--)
    {
        if(n%j==0&&is_prime[j]==true)
        {
            return j;
        }
    }
    return -1;
}
int main()
{
  int n;
  cin>>n;
  vector<bool> is_prime(n+1,false);
  is_prime[2]=true;
  for(int i=3;i<=n;i++) //找出到n范围内的所有素数
  {
      if(judge_su(i))
      {
          is_prime[i]=true;
      }
  }
  int max_su = get_max_prime(n,is_prime);
  if(max_su==-1)
  {
    cout<<-1<<endl;
    return 0;
  }
  vector<int> dp(n+1,INT_MAX);
  int ans=INT_MAX;
  for(int i=n-max_su+1;i<=n;i++)
  {
      if(!is_prime[i])//这个数不能是素数
      {
          int get_max = get_max_prime(i,is_prime);
          ans = min(ans,i-get_max+1);
          //dp[i]=i-get_max+1;
      }
  }
  cout<<ans<<endl;
  return 0;
}