2017第八届蓝桥杯C/C++ B组省赛 第二题

时间：2022-09-10 11:46:51

题目要求

标题：等差素数列

2,3,5,7,11,13,....是素数序列。
类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为30，长度为6。

2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。
这是数论领域一项惊人的成果！

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

长度为10的等差素数列，其公差最小值是多少？

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

题意理解 & 分析

本题要求找出长度为10的等差素数列，其公差最小值，首先使用线性素数筛求出一个较大范围（如 106 ）内的素数数列，然后寻找长度为10的数列，求出公差最小值。

完整代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std; 

const long long N = 1000010;
int check[N];
int prim[N],tot = 0;
void GetPrimeNumber(){
    memset(check,true,sizeof(check));
    check[0] = false;
    check[1] = false;
    for(long long i = 2;i < N;i++){
        if(check[i] == false) continue;
        prim[tot++] = i;
        for(long long j = i;j * i < N;j++){
            check[i * j] = false;
        }
    }
}
int main(int argc, char *argv[]) {
    GetPrimeNumber();
    cout << tot << endl;
    for(int j = 0;j < tot;j++){
        for(int i = 1;i * 10 < N;i++){
            int flag = 1,temp = prim[j];
            for(int k = 0;k < 9;k++){
                if(temp + i >= N || check[temp + i] == false){
                    flag = 0;
                    break;
                }else{
                    temp = temp + i;
                }
            }
            if(flag == 1){
                cout << i << ' ' << prim[j];
                return 0;
            }           
        }
    }
    return 0;
}

有趣的现象

做题过程中我把原本用int类型的check改成了bool类型，当i为素数时标记true，i为非素数标记false，发现输出的tot值为1，仔细思考后在求取素数之前对check数组进行初始化，默认所有i值属于素数，之后仅标记不是素数的成员：

memset(check,true,sizeof(check));

输出的tot值是正常的。
再次试验，声明bool类型的check数组立刻输出前20项：

bool check[N];
for(int i = 0;i < 20;i++){
        cout << check[i] << ' ';
    }

输出结果

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

调用memset函数初始化：

bool check[N];
memset(check,true,sizeof(check));
for(int i = 0;i < 20;i++){
        cout << check[i] << ' ';
}

输出结果：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

从中我们可以看出，当声明一个int或者bool数组之后，若没有赋初值，系统会默认填充0，可使用memset函数修改。

参考

http://blog.csdn.net/y1196645376/article/details/69718192

标签：

相关文章