黑马程序员技术交流社区

标题: 讨论一下素数 [打印本页]

---

作者: 邓士林    时间: 2015-1-9 22:31
标题: 讨论一下素数


晚上看到【羽狼之翼】哥们发的一个帖子，所以闲着没事就去思考了下，总结的不错，下面我就把我半个小时的思考分享给大家，请大家指导。（本来想去玩游戏的，嘿嘿）
/*
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
换句话说，只有两个正因数(1和自己)的自然数即为素数
*/
import java.util.*;
class  DemoPrime
{
        public static void main(String[] args)
        {
                Scanner sc =new Scanner(System.in);
                System.out.print("请输入一个大于1的数进行试验:");
                int i = sc.nextInt();
                System.out.println("prime1:" + bIsPrime1(i));
                System.out.println("prime2:" + bIsPrime2(i));
                System.out.println("prime3:" + bIsPrime3(i));
                System.out.println("prime4:" + bIsPrime4(i));
        }

        ///根据素数的定义进行判断
        public static boolean bIsPrime1(int n)
        {
                if(n<2)return false;
                if(n==2)return true;
                for(int i=2;i<n;i++)
                {
                        if(n % i == 0)
                        {
                                return false;
                        }
                }

                return true;
        }

        /*
        我们知道，偶数一定不是素数（可以整除2），所以我们可以再判断的时候筛选掉偶数
        */
        public static boolean bIsPrime2(int n)
        {
                if(n<2)return false;
                if(n==2)return true;
                if(n%2==0)return false;
                for(int i=3;i<n;i+=2)
                {
                        if(n%i==0)return false;
                }

                return true;
        }

        /*
        根据定理：: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
        */
        public static boolean bIsPrime3(int n)
        {
                if(n<2)return false;
                if(n==2)return true;
                for(int i=3;i*i<=n;i++)                                        //换成判断i<n/2+1也可
                {
                        if(n%i==0)return false;
                }

                return true;
        }

        /*
        用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为自然数)。
        */
        public static boolean bIsPrime4(int n)
        {
                if(n<2)return false;
                if(n==2 ||n==3)return true;
                if((n-1)%6==0 ||(n-5) % 6==0)return true;
                return false;
        }
        /*
        求素数的方法还有很多，大家可以去网上搜索资料，比如筛法求质数，效率最高，但会比较浪费内存
        */
}
代码：

测试结果图：

捕获.PNG (67.67 KB, 下载次数: 25)

下载附件

2015-1-9 22:29 上传

DemoPrime.zip

2015-1-9 22:31 上传

点击文件名下载附件

1.08 KB, 下载次数: 76

---

作者: 飞流至寒    时间: 2015-1-9 23:08
多谢楼主，学习一下！

---

作者: 些许    时间: 2015-1-9 23:19
也给你顶一个哈

---

作者: 李一白_    时间: 2015-1-15 18:52
多谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2