2017蓝桥杯省赛B组 --- 等差素数列

刺骨的言语ヽ痛彻心扉 2022-05-28 06:22 278阅读 0赞

> 标题：等差素数列  
> 2,3,5,7,11,13,….是素数序列。  
> 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。  
> 上边的数列公差为30，长度为6。  
> 2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。  
> 这是数论领域一项惊人的成果！  
> 有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：  
> 长度为10的等差素数列，其公差最小值是多少？  
> 注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。

##### 这题 先用循环 枚举出 10 ^ 6次方以内的素数 #####

##### 然后将素数用 数组 存起来 再枚举 #####

> 这题答案是: 210

#include<iostream>
    using namespace std;
    bool num[100010] = {
       false}; // 存放 素数 
    void create(){
       // 生成素数 
        int i = 0;
        int j = 0;
        int x = 0;
        for( i = 101; i < 100000; i +=2){
            x = sqrt(i);
            for(j = 2; j < x; j++ ){
                if(i % j == 0){
                    break;
                }   
                if(j != 2)
                    j++;
            }
            if(j >= x){
                num[i] = true;
            }
        }
    } 
    int main(){
        create();// 生成素数 
        int j = 0;
        int d = 1;
        int count = 0;
        int temp[15] = {
       0}; // 存放 已经找到 的 素数列
        int i = 101;
        while(1){
            for(i = i + 2; i < 100000; i += 2){
       // 找出 之前 生成的素数 
                if(num[i])  // 给出 素数 下标 及其值 
                    break;
            }
            for(d = 30; d < 1000; d++){ // 公差 看题 估计 为 30 - 1000 之间 这里 上限无所谓给多大都可以 
                for(j = i, count = 0; ; j+=d){
                    if(count == 10)     // 如果 找到 10 个连续的 就退出 
                        break;
                    temp[count] = j;// 存放找到的素数 
                    if(!num[j]){    // 如果 当前索引没有素数 就退出 
                        break; 
                    }else
                        count++;    // 否则 连续的个数 加一 
                }
                if(count == 10){
       // 如果找到连续 的 10个就退出 
                    cout << d << endl;
                    for(int x = 0; x < 10; x ++){
                        cout << temp[x] << "\t";// 打印找到 的 素数 
                    }
                    return 0;
                }
            }
        }
        return 0;
    }

> 第二次看到这个题 的解法 只改了 一个循环 但是 速度却快了 几倍  
> 还是暴力枚举 出10^6 以内的素数

#include<bits/stdc++.h>
    using namespace std;
    long n = 100000;// 生成素数的上限值
    bool num[100000+10] = {
       false};
    int i = 0, j = 0, temp = 0, x = 0;
    void f(){ // 枚举出所有的 素数
        for(i = 101; i < n; i += 2){
            temp = sqrt(i);
            for(j = 2; j < temp; j++){
                if(i % j == 0)
                 break;
            }
            if(j >= temp){
                num[i] = true;
            }
         }
    }
    int main(){
    
        // 等差 素数 第 二种解法:: 求连续 的 10个 数,, 那么可以 枚举 公差 ,
        // An = A1 + (n - 1) * d ;// 等差 公式
        f();
        x = 101;
        while(1){
            // 找出起始 素数
            for(x = x + 2; x < n; x +=2){
       // 和上面一样 找出 要 枚举 的素数
                if(num[x])
                    break;
            }
            //细微改动的循环
            for(i = 31; i < 1000 ; i++){ // 枚举公差
                for(j = 0; j < 10; j++){
       // 枚举 连续次数
                    if(!num[x + (i * j)]){
       //这里取代了上面复杂的几个判断 更简洁 
                        break;
                    }
                }
                if(j == 10){
                    cout << i << endl;
                    return 0;
                }
            }
    
        }