原题传送门

solution 1

看到题目，我想到的是一开始想（我太弱了）先预处理出 \(2\)~\(p\) 的所有 \(\leqslant \text{y}\) 的数，但时间复杂度是 \(\mathcal O (py)\)（这个是 \(p \times y\)），最差 \(\mathcal O ((10^9)^2) = \mathcal O (10^{18})\) 明显超时。。。

for(int i=2;i<p;i++){
        for(int j=i;j<y;j+=i){
            num[j]=1;
        }

solution 2

前置芝士（给小学生看的）：关于素数判定

求 x 是否是质数：

\(\text{定义}n = \left \lfloor \sqrt{x}\right\rfloor\)

\(\text{则若在 } \left[2,n\right] \text{ 中没有整除}n \text{的数，} \left[2,x\right]\text{ 中也没有，即 }x\text{ 为质数。}\)

$\text{证明：由于一个数的因数是一一对应的，即若}a \mid n\text{，则}(n \div a)\mid n\text{所以若}\left[2,n\right]\text{没有其因数，它就是素数，证毕。} $

思路

更具前置芝士，我们可以推断出若 \([2,\sqrt{y}]\)中没有\([2,p]\)的任意一个数的倍数，则\([2,y]\)中没有\([2,p]\)的任意一个数的倍数。

code

int p,y;
    cin>>p>>y;
    bool a=0;
    for(int i=y;i>p;i--){
        a=0;
        for(int j=2;j<=sqrt(i)&&j<=p;j++){
            if(i%j==0){
                a=1;
                break;
            }
        }
        if(!a){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1;

亿点点小优化

emm，这也不算优化，其实就是先用埃拉托斯特尼筛法处理出质数这样稍微快亿点点。

注：埃氏筛法时间复杂度是 \(\Theta(n\log \log n)\)证明

埃氏筛法只要到\(\sqrt{y}\)即可。

亿点点小优化2

其实从大往小遍历时遇到是合数但也可以的时候，可以把它的是合数的因数也筛掉