|
 | 作者: slatfish [slatfish]
 论坛用户 |
登录 |
| 小弟在求关于素数的时候遇到一个问题： 在求素数的时候，用的是筛选法，假如遇到求1~50的素数。我就会用所有的数字除以2，3，4，……49。这样只要是他们的倍数就会被筛选掉，只剩下素数。以上是一种方法。 而在解题的时候，题目给的答案是只要进行到50的平方根即可，也就是直到数字7。只要用2，3，4，5，6，7的倍数筛选掉1~50的数即可。结果答案是一样的。但我不知道为什么？请问一下大哥大姐们为什么？ |
| 地主 发表时间: 08/01 16:29 |
 | 回复: 286 [unique]  版主 |
登录 |
|
假设你要判断的是n,n开根号表示为sqrt(n)。 按你的方法去除，当除到大于sqrt(n)时，其商一定小于sqrt（n)，也就是说商已是你用过的数了。所以就没必要再除下去了。 如果看不懂，看下面的例子，假设判断197是不是质数。 经计算2、3、5、7、11、13、17都不能整除197，而197÷17＝11……10，商11比除数17小，如果继续除下去会更小。但此时的11已在前面用过了，因此没必要再继续下去了。 由此判断出197是质数。 |
| B1层 发表时间: 08/01 17:30 |
| 回复: 286 [unique] 版主 |
登录 |
|
还有，你的方法好象不叫筛选法，而叫穷举法。 筛选法一般用于求某一段内素数。 比如求2~1000以内素数。 先设一个数组，存储这999个数的符号位。初始时假设这些数全是素数。 然后从2开始，依次把该位的倍数符号位置为非素数。依次作完就得到全部素数。 比如第一轮，把2的所有2倍以上的数置为非素数。 第二轮，把3的所以2倍以上的数置为非素数。 第三轮，把5..... （注意4在第一轮已被2置为非素数，所以不参与筛选） |
| B2层 发表时间: 08/01 17:36 |
| 回复: slatfish [slatfish] 论坛用户 |
登录 |
|
3Q斑竹的回复。在下懂了。 |
| B3层 发表时间: 08/05 14:50 |
 | 回复: maomao520 [maomao520] 论坛用户 |
登录 |
|
他题不就是求1~50的素数吗？ 这个不也是个范围吗？能用筛选吧！ |
| B4层 发表时间: 08/06 14:06 |
| 回复: 286 [unique] 版主 |
登录 |
|
当然可以了,我只是说他的方法不是筛选法,没说不能用. :( |
| B5层 发表时间: 08/06 17:02 |
|
20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写：NetDemon
粤ICP备05087286号
论坛: 编程破解
标题: 关于求素数的问题？