数目最多的素数

mathe

转自:http://www.mymathforum.com/viewtopic.php?f=40&t=4528#p17489 请选择一个一位数a,一个两位数b,一个三位数c,一个四位数d,使得所有这4个数以及通过连接它们中的部分数,比如 $\bar{ab},\bar{cba}$等构成的数字中,素数的数目最多.

mathe

比如3,19,137,2017这四个数可以构成29个素数 3 193 1373 1920171373 20173 1920173 1913720173 19 2017137319 2017319 1372017319 3201719 1373201719 137201719 3137201719 137 3137 201719137 1932017137 3192017137 2017 1932017 1913732017 3192017 137192017 3137192017 1931372017 191372017 3191372017

无心人

似乎你这里描述的和那里有点不同吧

mathe

找到一个32个素数的 1,13,159,8559,score=32 131 8559159131 131591 8559131591 85591591 1385591591 1591385591 13 113 159113 8559113 15913 8559115913 855915913 1855915913 8559131159 85591159 13159 113159 8559113159 1855913159 1318559159 1138559159 15918559 1315918559 138559 1138559 1591138559 159138559 1159138559 1311598559 131598559

mathe

原帖由 无心人 于 2008-10-10 11:59 发表 似乎你这里描述的和那里有点不同吧

你说的是那边第一楼的问题?那个已经解决了,后面有有人提出了新的问题

medie2005

说一下我现在的大致思路。 考虑四个数都出现的形式$bar {abcd}$. $10^10$内的素数大概有$4*10^8$个。对每个$[10^9,10^10)$内的素数，将它划分成可能的$bar {abcd}$形式，这样，我们就确定了$a,b,c,d$.这样，这四个数的其他的排列组合形式就确定了，然后判素就可以了。

无心人

要想尽可能多 至少四个数字的末位必须是1，3，7，9 最好是素数 那么1位数字只有4种，二位数字最多21个，三位100多点，四位1000多点 总组合是800万多点 [ 本帖最后由 无心人 于 2008-10-10 14:06 编辑 ]

无心人

总共64 * 800万 而判素性， 初始化个素数表就可以了

mathe

其实就是要尽量快的判断素性.如果将$10^10$以前所有是否素数的信息都用比特位方式保存,内存消耗是个问题.而且使用大量内存也不见得很快.所以要看看是否有更好的方法.

无心人

不过是10^10 * 4 / 15 = 2.333GB内存么 用内存影射文件吧