CF948B Primal Sport

题目链接：http://codeforces.com/contest/948/problem/B

知识点：　　素数

解题思路：

　　\(f(x)\) 表示 \(x\) 的最大素因子。不难想到：\(X_1 \in [X_2 - f(X_2) + 1, X]\)，对于这个范围中的每一个非素数 \(X_1\) 求出其对应的最小的 \(X_0 = X_1 - f(X_1) + 1\)，找出一个最小的即为答案。

　　重点是要想到提前打出 \(f()\) 的表。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6+, inf = 0x3f3f3f3f;

 bool no_prim[maxn];

 int prim[maxn];

 int cnt=;

 int f[maxn];

 void init(){

     no_prim[]=no_prim[]=true;

     for(int i=;i<maxn;i++){

         if(!no_prim[i]){

             prim[cnt++]=i;

             for(int j=i*;j<maxn;j+=i){

                 f[j]=max(f[j],i);

                 no_prim[j]=true;

             }

         }

     }

 }

 int main(){

     init();

     int X;

     scanf("%d",&X);

     int ans=inf;

     for(int i=X-f[X]+;i<=X;i++){

         if(!no_prim[i]) continue;

         ans=min(ans,i-f[i]+);

     }

     printf("%d\n",ans);

     return ;

 }