黑马程序员技术交流社区

标题: 打印不大于给定值的所有素数并计数 [打印本页]

---

作者: hehaiwei    时间: 2016-3-7 20:08
标题: 打印不大于给定值的所有素数并计数
之前写的一个小函数, 效率不咋地, 大家随便看看吧
        /**
                打印不大于给定值的所有素数并计数
        */
        public static void printPrime(int max){
                if (max<2)        //最小的素数为2
                        return;
                //素数定理: max中素数数量小于max/(ln(max)-1.5)
                int length = (int)(max/(Math.log(max)-1.5));        
                length = (length > 2)?length:2;
                int[] prime = new int[length];        //存储已获得的素数
                int count = 0;
                System.out.print(2+"\t");
                a: for (int i=3; i<=max; i+=2){        //除2外所有素数都为奇数
                        for (int j=0; j<count && prime[j]*prime[j]<=i; j++){        
                                if (i%prime[j] == 0)        //判断是否是素数
                                        continue a;
                        }
                        System.out.print(i+"\t");
                        prime[count++] = i;
                }
                System.out.println();
                System.out.println("小于"+max+"的质数数量: "+(count+1));
        }

---

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

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