第60题-素数组合

问题描述

翻译为中文就是:

素数3、7、109、673很有名,因为任意2个素数按顺序组合得到的新的数也是素数,比如说去7和109,7109和1097都是素数,这4个素数之和是792这是有这种属性的4素数集合的最小值

求解:找出符合这种属性的最小的5素数集合

解题思路

这题花了挺多时间的,一开始没有思路,总感觉要用到回溯的算法但是又想不清楚,后来上网搜了一下答案,发现一个老外用F#实现了一个解法,暴力算法还挺神奇的,理解起来还很容易,所以我就用rust又实现了一遍

rust语言实现

p60.rs
use algorithms::math::prime::{get_prime_table, is_prime};

pub fn solution_of_p60() -> usize {
    let l = 10000;
    let primes = get_prime_table(l);
    for a in &primes {
        let pca = get_prime_combs(&primes, *a);
        for b in &pca {
            let pcb = get_prime_combs(&pca, *b);
            for c in &pcb {
                let pcc = get_prime_combs(&pcb, *c);
                for d in &pcc {
                    let pcd = get_prime_combs(&pcc, *d);
                    for e in &pcd {
                        println!("{}, {}, {}, {}, {}", a, b, c, d, e);
                    }
                }
            }
        }
    }
    return 1;
}

fn get_prime_combs(primes: &Vec<usize>, n: usize) -> Vec<usize> {
    let mut arr = vec![];
    for p in primes {
        if *p > n && is_valid_prime_pair(*p, n) {
            arr.push(*p);
        }
    }
    return arr;
}

看到代码就很清晰了,首先生成一个10000个数的素数表,定义一个迭代起点a,然后生成一个pca数组,pca里的每个元素都和a是拼接之后还是素数且每个元素都比a大。同理,迭代pca,得到一个pcb数组,这个数组中每个元素都和b是拼接后还是素数且每个元素都比a大。因为每一轮迭代都是基于上一轮的结果做的,所以可以保证 a, b组合是素数,b,c组合是素数,a, c组合也是素数

代码虽然有5重循环,但是实际上远远用不了10000^5次计算,因为越往后集合越小。目测数据不会很多刷新也不会很快,尝试了几组输出之后就试到了正确的结果。在这里为什么要定义素数表长度为10000呢,因为我测试了100,1000都没有得到结果,所以再测试10000的时候有输出了,不过我不知道何时计算会终止,所以只是用了一个print语句打印结果

做完之后看了一下讨论贴,发现有个哥们说他曾经花了4个礼拜的时间思考这个题目,又花了几小时跑程序,真是佩服他的毅力(15年前的代码我自然是看不懂的)

Last updated