算法练习题26——等差素数数列 (2017年蓝桥杯试题B)

时间：2024-09-29 20:08:40

题目描述

我们知道，素数是只能被1和它自身整除的正整数，比如：2, 3, 5, 7, 11, 13, 17, 19, 23, 29 等。

类似地，如果一个数列中的所有元素都是素数，并且这些素数构成了一个等差数列（即公差相等），这样的数列称为等差素数数列。比如，数列：7, 37, 67, 97, 127, 157 就是一个等差素数数列，它的公差为 30，长度为 6。

2004年，数学家格林与陶哲轩证明了任意长度的等差素数数列是存在的，这是数论中的一项重大成果。

现在，你的任务是编写一个程序，找出长度为10的等差素数数列，并且这个数列的公差最小。你需要输出该等差数列的公差值。

输出：

你需要输出一个整数，这个整数是长度为10的等差素数数列的最小公差。

注意：

        输出只有一个整数，不能包含其他多余的说明或内容。

示例：

题目给出的答案参考：

210

代码示例

c++

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

const int N = 10000;  // 素数查找的上限范围

// 判断一个数是否是素数的函数
bool isPrime(int n) {
    if (n <= 1) return false;  // 1 和更小的数不是素数
    if (n == 2) return true;   // 2 是素数
    if (n % 2 == 0) return false;  // 偶数不是素数（除了2）

    // 检查从 3 到 sqrt(n) 的所有奇数，是否有能整除 n 的数
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;  // 有其他数能整除，n 不是素数
        }
    }
    return true;  // 如果没有找到任何能整除的数，n 是素数
}

// 判断从 n 开始，公差为 cha 的等差数列中的 10 个数是否都是素数
bool ok(int n, int cha) {
    for (int i = 0; i < 10; i++) {  // 等差数列长度为 10
        if (!isPrime(n + i * cha)) {  // 检查 n + i * cha 是否是素数
            return false;  // 如果有一个不是素数，则返回 false
        }
    }
    return true;  // 如果 10 个数全是素数，返回 true
}

int main() {
    // 不断增大公差 cha，从 2 开始，寻找符合条件的最小公差
    for (int cha = 2;; cha++) {  // 无限循环，从小的公差开始
        for (int i = 2; i < N; i++) {  // 遍历从 2 到 N 的每个数 i，尝试作为等差数列的起始点
            if (ok(i, cha)) {  // 如果从 i 开始，公差为 cha 的 10 个数都是素数
                cout << cha << endl;  // 输出找到的最小公差
                return 0;  // 结束程序
            }
        }
    }
    return 0;
}

java

import java.util.*;

public class Main {
    
    // 判断一个数是否是素数
    public static boolean isPrime(int n) {
        if (n <= 1) return false;  // 1 和小于1的数不是素数
        if (n == 2) return true;   // 2 是素数
        if (n % 2 == 0) return false;  // 偶数不是素数（2除外）

        // 检查从 3 到 sqrt(n) 的所有奇数是否能整除 n
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;  // 如果找到能整除的数，n 不是素数
            }
        }
        return true;  // 如果没有找到任何能整除的数，n 是素数
    }
    
    // 判断从 n 开始，公差为 cha 的等差数列中的 10 个数是否都是素数
    public static boolean ok(int n, int cha) {
        for (int i = 0; i < 10; i++) {  // 检查等差数列长度为 10
            if (!isPrime(n + i * cha)) {  // 检查每个 n + i * cha 是否是素数
                return false;  // 如果有一个数不是素数，返回 false
            }
        }
        return true;  // 如果 10 个数全是素数，返回 true
    }
    
    public static void main(String[] args) {
        int N = 10000;  // 素数查找的上限范围
        
        // 不断增大公差 cha，从 2 开始，寻找符合条件的最小公差
        for (int cha = 2;; cha++) {  // 无限循环，从小的公差开始
            for (int i = 2; i < N; i++) {  // 遍历从 2 到 N 的每个数 i，尝试作为等差数列的起点
                if (ok(i, cha)) {  // 如果从 i 开始，公差为 cha 的 10 个数都是素数
                    System.out.println(cha);  // 输出找到的最小公差
                    return;  // 结束程序
                }
            }
        }
    }
}

相关文章