程序员节该问题如何解？

Question

求一组互不相同的质数，其和为质数且尽可能小，使得这些质数的平方根之和的小数部分前14位数字序列为20251024HHMMSS。
其中，HHMMSS表示一个合规有效的时刻，例如，HHMMSS=210536。

编程找了找了几组，但和值最小的比较费时。

prime_sum = 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+59+389+1151+1613+4177 = 7717
sqrt_sum = 231.2025102420273165…

prime_sum = 2+3+5+7+11+13+17+19+23+29+31+37+103+149+3463+5437 = 9349
sqrt_sum = 200.2025102404065602…

prime_sum = 2+3+5+7+11+13+17+23+229+239+463+4519 = 5531
sqrt_sum = 143.2025102418012322…

Answer 1

参考知乎上fortran代码，转成C++，速度是原来3倍，不到30秒，得解。
代码如下：

#include <iostream>
#include <vector>
#include <cmath>
#include <chrono>
#include <iomanip>

class AAData {
public:
    static const int nn = 79;
    std::vector<int> a;
    std::vector<int> c;
    std::vector<double> b;
    std::vector<double> s;
    int m;
    long long k;
    
    AAData() : a(nn + 1, 0), c(nn + 1, 0), b(nn + 1, 0.0), s(1001, 0.0), m(0), k(0) {}
};

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    int sqrt_n = static_cast<int>(std::sqrt(n));
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

bool cc(int n, AAData& data, bool& found) {
    for (int i = data.a[n-1] + 1; i <= data.m - data.c[n-1]; i++) {
        if (data.s[i] == 0) continue;
        
        data.a[n] = i;
        data.b[n] = data.b[n-1] + data.s[i];
        data.b[n] = data.b[n] - static_cast<int>(data.b[n]);
        
        long long k_val = static_cast<long long>(data.b[n] * 1e8);
        data.c[n] = data.c[n-1] + i;
        
        if (k_val == 20251024LL) {
            if (data.s[data.c[n]] == 0) continue;
            
            long long k_val2 = static_cast<long long>(data.b[n] * 1e14);
            k_val2 = k_val2 % 1000000;
            
            if (k_val2 / 10000 > 23) continue;
            
            long long k_val3 = k_val2 % 10000;
            if (k_val3 / 100 > 59) continue;
            if (k_val3 % 100 > 59) continue;
            
            data.m = data.c[n];
            
            // 输出结果
            std::cout << "\n";
            for (int j = 1; j < n; j++) {
                std::cout << data.a[j] << "+";
            }
            std::cout << data.a[n] << "=" << data.m << std::endl;
            std::cout << "n=" << n << std::endl;
            
            // 计算平方根和，使用long double提高精度
            long double sqrt_sum = 0.0L;
            for (int j = 1; j <= n; j++) {
                sqrt_sum += std::sqrt(static_cast<long double>(data.a[j]));
            }
            std::cout << "sum=" << std::setprecision(20) << sqrt_sum << std::endl;
            
            found = true;
            return true;
        }
        
        if (n < data.nn && !found) {
            if (cc(n + 1, data, found)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    auto start_time = std::chrono::high_resolution_clock::now();
    AAData data;
    
    // 计算1到1000的平方根小数部分，只保留质数的
    for (int i = 1; i <= 1000; i++) {
        data.s[i] = std::sqrt(static_cast<double>(i));
        
        // 检查是否为质数
        if (!isPrime(i)) {
            data.s[i] = 0;
        } else {
            data.s[i] = data.s[i] - static_cast<int>(data.s[i]);
        }
    }
    
    // 计算前79个质数的和
    for (int i = 1; i <= data.nn; i++) {
        if (data.s[i] != 0) {
            data.m += i;
        }
    }
    
    std::cout << "m=" << data.m << std::endl;
    
    bool found = false;
    cc(1, data, found);
    
    auto end_time = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::seconds>(end_time - start_time);
    std::cout << "\ntime=" << duration.count() << "s" << std::endl;
    
    return 0;
}

计算结果：

m=791

2+3+7+19+41+59+73+131+181+241=757
n=10
sum=73.20251024075556

time=27s