您现在的位置:首页 --> 查看专题: 素数
最近看到一则颇为有趣的新闻,说北大一名大一新生,以素数为标准选手机号,受到广大网友膜拜。其实素数的检测算法是很有趣的,并且会涉及到数论、概率算法等诸多内容,一直觉得素数探测算法是了解概率算法很好的入口。本文和大家简单聊聊如何确定一个数是素数。
今天又学到一种证明素数无穷多的方法。它是由 Filip Saidak 发现的,论文曾发表在 2006 年的 The American Mathematical Monthly 上。 首先注意到,两个相邻自然数一定是互质的(否则,假设他们有大于 1 的公因数 k ,则他们的差也能被 k 整除,这显然是不可能的)。现在,取一个自然数 n > 1 。由于 n 和 n + 1 是相邻自然数,因此 n 和 n + 1 是互质的。也就是说,n 的质因数和...
用6N±1法求素数任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…) 显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速...
[ 共3篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [66] Oracle MTS模式下 进程地址与会话信
- [65] Go Reflect 性能
- [64] 如何拿下简短的域名
- [60] android 开发入门
- [59] 图书馆的世界纪录
- [59] 【社会化设计】自我(self)部分――欢迎区
- [58] IOS安全–浅谈关于IOS加固的几种方法
- [54] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [47] 读书笔记-壹百度:百度十年千倍的29条法则
赞助商广告