黑马程序员技术交流社区

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

---

作者: 云狐    时间: 2015-8-28 00:04
标题: 打印不大于给定值的所有素数并计数
之前写的一个小函数, 效率不咋地, 大家随便看看吧

1.         /**
   
2.                 打印不大于给定值的所有素数并计数
   
3.         */
   
4.         public static void printPrime(int max){
   
5.                 if (max<2)        //最小的素数为2
   
6.                         return;
   
7.                 //素数定理: max中素数数量小于max/(ln(max)-1.5)
   
8.                 int length = (int)(max/(Math.log(max)-1.5));       
   
9.                 length = (length > 2)?length:2;
   
10.                 int[] prime = new int[length];        //存储已获得的素数
    
11.                 int count = 0;
    
12.                 System.out.print(2+"\t");
    
13.                 a: for (int i=3; i<=max; i+=2){        //除2外所有素数都为奇数
    
14.                         for (int j=0; j<count && prime[j]*prime[j]<=i; j++){       
    
15.                                 if (i%prime[j] == 0)        //判断是否是素数
    
16.                                         continue a;
    
17.                         }
    
18.                         System.out.print(i+"\t");
    
19.                         prime[count++] = i;
    
20.                 }
    
21.                 System.out.println();
    
22.                 System.out.println("小于"+max+"的质数数量: "+(count+1));
    
23.         }

复制代码

不打印只计数的话可以快一些

---

作者: 云狐    时间: 2015-8-28 00:09
计算运行时间的话用的是这个

1.         public static void main(String[] args){
   
2.                 long start = System.currentTimeMillis();
   
3.                 printPrime(10000000);
   
4.                 long end = System.currentTimeMillis();
   
5.                 System.out.println("程序运行时间: "+(end-start)+"ms");
   
6.         }

复制代码

---

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

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