心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

今天第一次写出miller-rabbin素数测试,知道这个概率算法对于大整数测试是否是素数十分有效,成功率有保证~于是突然想到有没有手机号是素数!
电脑开了半个小时,用miller-rabbin测试,CPU一直保持占用率100%,结果搜结束之后我的data.out里面还是什么都没有!
拿出纸笔,开始计算:如果手机号只有如下几个限制:1、以1开头;2、共11位。根据素数定理,手机号是素数的概率为0.04(以1开头的11位整数大约有4亿个是素数)。
很明显,miller-rabbin出错了!用5000-10000之间的素数对拍了一下,算法没有出错。毫无疑问,快速幂取模时溢出了!
换用O(n^0.5)的素数判断,很快找到了许多素数手机号,列出几个好的手机号吧:

15956880001;

15956880007;

15256880101;

15256888811;

15256885577

还有很多……



posted on 2010-02-20 23:26 lee1r 阅读(486) 评论(0)  编辑 收藏 引用 所属分类: Programming Diary

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理