数目最多的素数

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内存么
用内存影射文件吧