BROJ 题解

翻译。

题解部分

思路：

算法1

暴力枚举。

对于每个 $i$ 找到其最小质因子 $P$，时间复杂度$O(n \sqrt{n})$。

算法2

线性筛。

筛出 $[1,10^{9}]$ 的所有素数，对于每个 $i$，找到其最小质因子为 $P$ 切其相对序列值属于前一部分得到的素数表前 $N$ 个数。

时间复杂度 $O(n \log n)$，可以通过此题。

代码

数据较水，直接暴力可以过

#include <iostream>
using namespace std;
int main(){
    int n,p,sm=0;
    cin >> n >> p;
    if (n*p>1e9){
        cout<<0<<endl;
        return 0;
    }
    for (int i=0;i<n;++i){
        sm+=p;
        if (sm>1e9){
            cout<<0<<endl;
            return 0;
        }
        for (int j=2;j<p;++j){
            if (sm%j==0){
                --i;
                break;
            }
        }
    }
    cout<<sm<<endl;
    return 0;
}