A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黄河一抔泥 初级黑马   /  2014-5-26 17:08  /  3234 人查看  /  9 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

为什么判断一个数是不是质数(假设为i),只要判断他能不能被2~根号下i整除就行了,  判断2~i/2能不能整除理解,就是这个有点理解不了

评分

参与人数 1技术分 +1 收起 理由
李小然 + 1 赞一个!

查看全部评分

9 个回复

倒序浏览
这是规律总结,是一个结论,只要记住就可以啦,这里面涉及的是数学知识,而非计算机的知识。
回复 使用道具 举报 1 0
2~根号下i,范围不够,很多数漏掉了 ,比如15,i 肯定不是偶数  ,所以到一半就可以了,
回复 使用道具 举报
错了  ,脑残了
回复 使用道具 举报
两个 代码都试一次  运行后  应该就有不同的了
回复 使用道具 举报
对于质数的思路的是这样的:
1.质数就是只能被1和本身整除
2.让一个数从1开始除到自身
3.定义一个计数器记录除的次数
4.判断计数器只要为2就确定是质数了
回复 使用道具 举报
这就是定律 无需理解  你要搞清自己的专业方向  不是数学
回复 使用道具 举报
首先要理解什么是质数:质数又称素数,有无限个。一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除(除0以外)的数称之为素数(质数);
这样子我们就可以看到不能被其它自然数整除那么我们分析如下:
1、肯定要除以比自己小的数
2、0和1除外
3、因为2就是质数、所以当是2的时候直接返回
4、我们要除以2-i所有的数,但是我们发现数是对称的,比如24,2*12、3*8、4*6、6*4、8*3、12*2
这些都是能得到24的数,所以我们只用计算到2-12就行了,不用再除以12以上的数,因为再除就是相同的
基于以上四点程序就可以写出来了
     public static void main(String[] args)
    {
     Random rd = new Random(); //定义一个随机变量
     int i = rd.nextInt(1000);  //获取个随机数
             System.out.println(isNum(i)); //输出结果
            

    }      
    public static String isNum(int i )
    {
           
        String ret =i+"是质数"; //默认是质数
        if(i==2)           
                return ret;          //如果是2返回默认结果
            for (int j = 2; j < i/2; j++) { //制订循环次数
                        if(i%j==0)
                        {
                                ret=i+"不是质数";  // 如果能够整除返回不是质数
                                break;
                        }
                }
            return ret;    //返回结果
    }

评分

参与人数 1技术分 +1 收起 理由
黑妞~ + 1

查看全部评分

回复 使用道具 举报 1 0
e10my 中级黑马 2014-5-26 20:51:10
9#
本帖最后由 e10my 于 2014-5-27 07:01 编辑

@author e10my
楼上好像都没有解决楼主的问题。
我来试着抛个砖、
试着使用反证法:假设我们求出来的数 I 是合数(即可以被小于它的一个数整除。且这个数不为1),
并且这个数不可以被小于 【根号 I 】的任意数整除(定义是不可以被小于 【根号 I】 的任意数整除就是素数,我们现在举个反栗子)
那么这个数又是合数, 所以一定会被一个Q属于【根号 I ~I】的一个数整除(整除结果为W)
而【根号 I】 乘以 【根号 I】 就是 I
所以 这个整除出来的结果W 必然属于 【0~根号 I】 。(即这个数可以被一个【0~ 根号 I】的数整除)
然而 我们之前已经验证过了 这个数 I 不会被 【0~ 根号 I】 的任意数整除
So : 埃拉托斯特尼筛法 是正确的。
PS :这个定理就是埃拉托斯特尼筛法。
via:http://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95
PPS: 同学们在学习编程的时候可以适当补充一下数学知识,以免用到的时候方恨少啊。(不要做一个只会撸码的程序员!)
这个筛选法的正证法我也不太会,如果有朋友有比较好的正证法还望一同讨论。{:2_40:}
PPPS :抛砖晚了一步,楼上@向前看向前走 已经说的很明白了。不难理解。顺便吐槽渣编辑器, 没有数学公式。
回复 使用道具 举报
icm 中级黑马 2015-12-17 22:36:07
10#
学习学习。。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马