2017B 等差素数列

http://oj.ecustacm.cn/problem.php?id=1326

等差素数列

不一定是相邻的素数

答案是210

以j为起点，i为公差，向后找9个数字

每个数字比最大的小，并且是质数

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;

bool is_prime(int x){
    for(int i = 2; i <= sqrt(x);i++){
        if(x % i == 0)
            return false;
    }
    return true;
}
int p[maxn],v[maxn];
int m = 0;

int main(){
    freopen("out","w",stdout);
    for(int i = 2; i < maxn; i++){
        if(is_prime(i)) {
            p[m++] = i;
            v[i] = 1;//表示是质数
        }
    }

    for(int i = 1; i * 10 < maxn; i++){
        for(int j = 0; j < m; j++){
            int flag = 1,temp = p[j];
            for(int k = 1; k < 10; k++){
                if(temp + i >= maxn || !v[temp +i]){
                    flag = 0;
                    break;
                }else{
                    temp += i;
                }
            }
            if(flag) {
                cout << i << endl;
                return 0;
            }
        }
    }
    return 0;
}