第60题-素数组合
问题描述
翻译为中文就是:
素数3、7、109、673很有名,因为任意2个素数按顺序组合得到的新的数也是素数,比如说去7和109,7109和1097都是素数,这4个素数之和是792这是有这种属性的4素数集合的最小值
求解:找出符合这种属性的最小的5素数集合
解题思路
这题花了挺多时间的,一开始没有思路,总感觉要用到回溯的算法但是又想不清楚,后来上网搜了一下答案,发现一个老外用F#实现了一个解法,暴力算法还挺神奇的,理解起来还很容易,所以我就用rust又实现了一遍
rust语言实现
p60.rs
看到代码就很清晰了,首先生成一个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