第50题-连续素数和

本文包含欧拉项目第50题解法

问题描述

第50题图

翻译为中文是：

41 是6个连续素数之和，41 = 2 + 3 + 5 + 7 + 11 + 13 ，它是两位数中能表示成最长的连续素数和的数字，1000以内最大的这样的数字是953，可以被表示为21个连续素数和

求解：100万以内，能被表示为最长的连续素数和的数是多少

解题思路

题目看起来很像最长连续子列问题，但是仔细想想又不太一样，对于最大连续子列问题有线性时间解法，但是这个问题我只想到了一个 $O(n^2)$ 的解法，所幸100万规模不大，运算时间也不算太长

rust语言实现

p50.rs

use algorithms::math::prime::{get_prime_table_le, is_prime};

pub fn solution_of_p50(uplimit: usize) -> usize {
    let primes = get_prime_table_le(uplimit);
    let l = primes.len();
    let mut longest_seq_sum = 0;
    let mut longest_seq = 0;

    for i in 0..l - 1 {
        let mut sum = primes[i];
        for j in i + 1..l {
            sum += primes[j];
            if sum > uplimit {
                break;
            }
            if is_prime(sum) {
                if longest_seq < j - i {
                    longest_seq = j - i;
                    longest_seq_sum = sum;
                }
            }
        }
    }
    return longest_seq_sum;
}

代码很直观，利用了之前写的2个工具方法生成某个数以内的素数表，判断一个数是否是素数。代码中有个很有意思的地方，在计算i到j之间的和时，没有多加一个临时变量k多加一层循环，而是在i循环开始时初始化一个sum，每次循环j的时候加上这个sum，这样可以节省一次循环优化性能

这个程序也有对应的单测，但是为了避免泄露答案就不写了，有兴趣的小伙伴可以自己补上