博客

蓝桥杯 04/08/2017

标题：等差素数列

2,3,5,7,11,13……是素数序列。

类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。

上边的数列公差为30,长度为6。

2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。

这是数论领域一项惊人的成果！

有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：

长度为10的等差素数列，其公差最小值是多少？ ——————即只需要求出最小公差值

注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。

有一个很关键的规律：对于长度为k的素数等差数列，它们的公差能被小于k的所有素数整除

详见

百度百科

完整代码： 另见

GitHub

// 对于长度为k的等差素数数列，
// 它的公差能被小于k的所有素数整除。
#include<iostream>
#include<vector>
using namespace std;

bool isSushu(int s);

int main() {
    int k;
    int n=0;
    int g=1;
    vector<int> su;
    vector<int> lie(k);
    cout<<"请输入等差素数列的长度:"<<endl;
    cin>>k;
    for(int i=2;i<k;i++) {
        if(isSushu(i)) {
            su.push_back(i);
        }
    }
    // 以下求出一个最小的能被所有小于序列长度k的素数整除的公差
    while(true) {
        int n=0;
        for(auto sus: su) {
            if(g%sus==0) n++;
        }
        if(n>=su.size()) {
            cout<<g<<endl;
            break;
        }
        else {
            n=0;
            g++;
        }
    }
    /*----以下是输出满足的序列----*/
    int ii;
    int i=2;
    int n1=0;
    ii=i;
    while(n1<k) {
        if(isSushu(ii)) {
            lie.push_back(ii);
            n1++;
            ii+=g;
        }
        else {
            lie.clear();
            n1=0;
            i=i+1;
            ii=i;
        }
    }
    for(auto i1:lie) cout<<i1<<' ';
    cout<<endl;
    return 0;
}

bool isSushu(int s) {
    int u;
    for(u=2;u<=s-1;u++) {
        if(s!=u && s%u==0) {
            return false;
        }
    }
    //printf("%d ",s);
    return true;
}