黑马程序员技术交流社区

标题: 求质数的疑惑 [打印本页]
作者: 吴刚    时间: 2012-11-11 18:55
标题: 求质数的疑惑
本帖最后由 吴刚 于 2012-11-11 19:01 编辑
  1. public class LoopDemo {
  2.   public static void main(String[] args) {
  3.     for(int n = 2; n<1000; n++){
  4.       //n: 2~<1000
  5.       //如果n能够被 m:2~n/2 某个数整除.
  6.       //就忽略n, 找下一个n
  7.       int m = 2;
  8.       boolean found = false;//1
  9.       while(m<=n/2){
  10.         if(n%m==0){
  11.           found = true;//2
  12.           break;
  13.         }
  14.         m++;
  15.       }
  16.       if(!found){//3，没有找到任何整除的情况,关键就这一句
  17.         System.out.print(n +",");
  18.       }
  19.       //如果找到n就输出n
  20.     }
  21.   }

  23. }
复制代码
句3的if后面的表达式判断为真的时候才会执行方法体，但是用boolean标记这点有点迷惑，句1所有数字标记为假，句2不是质数的为真，其他为质数，那句3的表达式不是把所求的质数又标记为true了吗？另外自己修改了一下求素数的方法。感觉更好,代码如下，关于下面的代码有一个疑问，效率是不是没有上面的高？谢谢
  1. public class LoopDemo2 {

  3.         /**
  4.          * @param args
  5.          */
  6.         public static void main(String[] args) {
  7.                 // TODO Auto-generated method stub
  8.                 int i;
  9.                 for (i=2; i<=1000; i++){//输出1-1000的素数
  10.                         if(loop(i)){
  11.                                 System.out.print(i+",");
  12.                         }
  13.                 }

  15.         }
  16.         public static boolean loop(int i){//判断是否为素数
  17.                 int j;
  18.                 for (j=2; j<=1000; j++){
  19.                         if(0 == i%j)
  20.                                 break;
  21.                 }
  22.                 if (j == i){
  23.                         return true;
  24.                 }else{
  25.                         return false;
  26.                 }
  27.         }

  29. }
复制代码
作者: 冯纪纲    时间: 2012-11-11 20:20
其实这两个嵌套的循环，对计算机强大的计算能力而言是微不足道的，尽管的他的时间复杂度是n的平方。
楼主上面的两种方法，我测测试仪一下，第一种方法大致消耗的时间在0~16毫秒之间，第二种方法大致消耗的时间也在0~16毫秒之间。由于这代码执行的太少，看不出来什么效果，我就分别把这两种方法给执行了1000次，发现他们消耗的时间大致都在2500毫秒~4000毫秒之间。其实都差不多

我感觉楼主的方法有点麻烦，自己也想了一个方法。还有就是判断素数条件，是如果他不能够被2到这个数的平方值(就是开根号)这个区域的数整除的话，就是素数。
  1. public static void main(String[] args) {
  2.                 long start = System.currentTimeMillis();//记录代码开始执行的时间
  3.                 int i, j;
  4.                 for (i = 1; i <= 1000; i++) {
  5.                         int key = (int) Math.sqrt(i);//开根号
  6.                         for (j = 2; j <= key; j++) {
  7.                                 if (i % j == 0) {
  8.                                         break;
  9.                                 }

  11.                         }
  12.                         if (j > key) {//如果在这个区间没有被整除的话，那么这个数肯定是素数
  13.                                 System.out.println(i);
  14.                         }
  15.                 }
  16.                 long end = System.currentTimeMillis();
  17. //记录代码执行后的时间
  18.                 System.out.println();
  19.                 System.out.println("耗时：" + (end - start));
  20.         }
复制代码




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