2017 年蓝桥杯 C 语言 B 组省赛第 2 题: 等差素数列

题目

标题:等差素数列

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

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

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

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

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

题目分析

首先, 素数 (质数) 都是大于 1 的, 因此 1 不是素数, 这点在题目中也有说明.
本题的解题思路是这样的:
我们首先需要定义一个用于判断一个数是不是素数的函数, 下面这个函数就可以判断一个大于 2 的数是不是一个素数, 如果是素数就返回真:

bool f(int x){
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

这里需要注意的是, 如果把上面这个判断素数的函数写成下面这样是不对的, 因为如果一个数能够整除除了自身和 1 之外的其他数则可以断定该数不是素数, 但是如果一个数不能够整除除了自身和 1 之外的其他数中的一个, 是不能判断其是不是素数的, 错误的素数判断程序如下:

bool f(int x){
    for(int i=2;i<x;i++){
        if(x%!=0){
            return 1;
        }
    }
    return 0;
}

之后, 我们需要从素数的起始位置, 也就是数字 2 开始, 从小到大依次判断前 1 个数加 1 是不是素数, 如果不是素数且之前计算出来的数字个数小于 10, 那么第 2 个素数开始进行上面的逐个加 1 的操作, 直到第 99999 个数字 (这个数字不一定是素数, 如果不是素数不参加之前的运算) 为止, 如果不能以 1 为公差找到 10 个数字, 则之后还是从数字 2 开始逐个加 2 并判断是不是素数, 如果不是素数则从第二个素数开始逐个进行加 2 的操作, 直到第 99999 个数字为止, 如果不能以 2 为公差找到 10 个数字, 则之后从数字 2 开始进行加 3 的操作…直到第 99999 个数字为止.

如果计算之后找不到结果可以将上面提到的有关搜索范围适当扩大.

在具体的编程实现上有以下两种.

程序 1:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int a[99999];
bool f(int x){
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
}

int main(){

    for(int a=2;a<99999;a++){ //遍历首项
        for(int b=1;b<999;b++){ //遍历公差

//使用十层 if 判断寻找符合条件的数值, 能抵达第十层的说明满足条件, 输出之
            if(f(a)){
                if(f(a+b*1)){
                    if(f(a+b*2)){
                        if(f(a+b*3)){
                            if(f(a+b*4)){
                                if(f(a+b*5)){
                                    if(f(a+b*6)){
                                        if(f(a+b*7)){
                                            if(f(a+b*8)){
                                                if(f(a+b*9)){
                                                    cout<<b<<endl;
                                                }else{
                                                    continue;
                                                }
                                            }else{
                                                continue;
                                            }
                                        }else{
                                            continue;
                                        }
                                    }else{
                                        continue;
                                    }
                                }else{
                                    continue;
                                }
                            }else{
                                continue;
                            }
                        }else{
                            continue;
                        }
                    }else{
                        continue;
                    }
                }else{
                    continue;
                }
            }else{
                continue;
            }
        }
    }

    return 0;
}

程序 2:

#include<iostream>
#include<bits/stdc++.h>
#define MAX 999999
using namespace std;
int a[MAX];

bool f(int x){ //判断一个数字是不是素数的函数
    for(int i=2;i<x;i++){
        if(x%i==0){
            return 0;
            //如果能整除, 则表示这是一个非素数, 返回假 (0)
        }
    }
    return 1;
    //如果不能整除, 则表示这是一个素数, 返回真 (0)
}

int main(){

//遍历从 2 到 99999 之间的数字, 将其中的素数标记为 1
    for(int i=2;i<99999;i++){
        if(f(i)){
            a[i]=1;
        }
    }

    for(int delta=1;delta<999;delta++){
    //遍历从 1 到 999 之间的公差
        for(int i=2;i<99999;i++){
        //遍历数组 a[i]

            int step;
            for(step=0;step<10;step++){
            //限制只遍历数组 a[i] 中的 10 个数字

                //如果第 i+delta*step 个数字不是素数就退出
                if(a[i+delta*step]!=1){
                    break;
                }
            }

            //如果能完整的走完 10 步则表示找到了答案
            if(step==10){
                cout<<delta<<endl;
                return 0;
            }
        }
    }
    return 0;
}

本题的正确答案:
210