[原创] 64位质数知多少，龙之梦工作室告诉您
[ 2007-10-13 15:18:17 ]
引言/提要：所有精确数据，是由龙之梦工作室自主开发的Super Prime超级质数机实际计算得出。
关键词：Super Prime，超级质数机，测试软件，性能测试，质数，64位，奥林匹克，核心技术
问：求64位质数的程序有什么用？
答：对于不同的人，有不同的作用。可以拿“天天跑步有什么用”这个问题来作类比。
如果您是个对身体健康毫不关心的人，那么，天天跑步只是个遥不可及的空想，对您没有什么用。
如果您是个热爱运动的普通人，那么，天天跑步可以使您身体强健。
如果您是刘翔，那么，天天跑步是您夺取奥运金牌必不可少的基本功训练。
类似的：
如果您对电脑的性能毫不关心，能用就行，那么，求64位质数程序对您没有什么用。
如果您是个电脑爱好者，那么，求64位质数程序可以帮您测试电脑性能。
如果您是个程序员，甚至是奥林匹克计算机竞赛选手，那么，求64位质数程序的编写、算法优化，是您提高水平的一种基本功训练。
问：最大的16位质数是多少？
答：是16进制数0xfff1。
问：普通PC机求出所有16位质数需要多长时间？
答：用一台Athlon XP 1700+，使用Super Prime超级质数机进行计算，少于1秒钟。
问：16位质数有多少个？
答：包括2在内，共6542个质数，约占全部16位非负整数的9.98％。
问：最大的32位质数是多少？
答：是16进制数0xfffffffb。
问：普通PC机求出所有32位质数需要多长时间？
答：随着硬件的进步，以及Super Prime超级质数机软件算法的升级改进，这个成绩不断被刷新。
用一台2004年的Athlon XP 1700+，1GB DDR 333MHz内存，使用Super Prime超级质数机进行计算，包括存入硬盘的时间，用了接近9个小时。
而用一台Athlon64 X2 3800+，1GB DDR2 800MHz内存，用版本为V20070613的超级质数机，开通双线程并行计算，包括存入硬盘的时间，只用了大约3小时13分钟。
如果使用四核CPU，开通四线程并行计算，时间还会再减半。
问：32位质数有多少个？
答：包括16位质数在内，共203,280,221个质数，约占全部32位非负整数的4.73％。
问：最大的64位质数是多少？
答：是16进制数0xffffffffffffffc5。
问：普通PC机求出一个64位质数需要多长时间？
答：用一台Athlon XP 2000+，1GB DDR 400MHz内存，使用Super Prime超级质数机进行计算，求一个64位质数大约要用12秒。
根据最新的测试数据，用一台Athlon64 X2 3800+，1GB DDR2 800MHz内存，在单线程下运行已逼近10秒大关，达到了10.062秒。在双线程下运行更是充分发挥出双核的威力，平均每个64位质数仅5.952秒。如果使用四核CPU，速度还将进一步提高。
问：普通PC机求出所有64位质数需要多长时间？
答：不知道。以目前的电脑运算能力，即使是世界上最强的超级计算机，要想求出所有64位质数也是不可能的，需要的时间是个天文数字。
知道数学上的梵塔问题吗？知道国际象棋棋盘上放谷子的问题吗？求所有64位质数所需的时间，数量级上完全可以和这两个问题相媲美。
梵塔问题：传说古印度有3支金针，第一支插有64片大小不同的金片，大的在底下，小的在上面。然后由僧人日夜不停地在3支金针之间移动金片，要求大的金片不能压在小金片上面。据说把全部64块金片移到另一支金针上的时刻，世界末日就会来临。
国际象棋棋盘上放谷子的问题：传说古时候有个国王要赏赐一位大臣，大臣说只要赏赐谷子就够了。在国际象棋棋盘的64个格子里，第一个格子放1粒谷子，第二个格子放2粒，第三个格子放4粒，依此类推，不断翻倍，直到谷子放满64个格子为止。
这两个问题，移动金片的次数和谷子的粒数都是2的64次方减1。这个数字是什么概念呢？假设梵塔的金片每秒移动一次，那么移动这么多步需要多少秒，折合成多少年，您自己算一下。总之从宇宙大爆炸至今，宇宙的年龄不过150亿年，还不及这个时间的一个零头。如果真的能够完成移动64片金片的所有步数，不要说世界末日，可能宇宙的末日都要到了。
求64位质数的问题与此类似。假设求质数程序能够平均每秒扫过1个整数（扫过的意思，就是确定了这个整数是否质数），那么求所有64位质数所需要的时间，就跟梵塔问题的移动金片时间相同。
问：64位质数有多少个？
答：由于目前不可能求出所有64位质数，所以也不知道64位质数的确切个数。只知道在0xfffffffffffff000-0xffffffffffffffff这4096个64位整数的范围内，有98个质数，约占这些整数的2.39％。
虽然不清楚64位质数的确切个数，但可以用数学方法作出近似的估算。早已经有数学家证明了如下的质数定理：设f(x)是比x小的质数个数，ln(x)是x的自然对数。则当x趋向于无穷大时，f(x)的值趋向于x/ln(x)。
根据这个质数定理，我们可以估算，令x等于16进制数0xffffffffffffffff，则x/ln(x)约等于415,828,534,307,635,078。即包括16位质数、32位质数在内，64位质数的个数在415,828,534,307,635,078附近，约占全部64位非负整数的2.25％。光是保存这些质数，就需要3,025,551TB的存储空间。
正因为64位质数的搜索空间还算比较大，所以用在安全加密方面还是有一定的保护作用。不象32位数只有4G空间（指编码空间，存储空间应该是16GB），可以做出完整的对照表，根本不需要穷举攻击，直接查表就可以破解。
以上信息之中的精确数据，是由龙之梦工作室自主开发的Super Prime超级质数机实际计算得出。
|
|
[2014-10-16]
人次