题目：判断101-200之间有多少个素数，并输出所有素数。public static int getShuShu(int start,int end){ int count=0;
p:for(int i=start;i<end;i++){
if(i==1){continue;}
for(int j=2;j<=(int)(i/2);j++){
if(i%j==0){
  continue p;//不是素数
}
}
count++;
System.out.println(i);
}
return count;
}

请问你想要更简单的方法还是要效率更高的方法，如果想效率更高的话，可以i/2替换为Math.sqrt(i)!

zhaozhao 发表于 2014-12-14 12:15
请问你想要更简单的方法还是要效率更高的方法，如果想效率更高的话，可以i/2替换为Math.sqrt(i)! ...

不错哦。。。

这里给出了比较高效的求法，一个是常规的，一个是筛法。

1. import java.util.ArrayList;
   
2. import java.util.Iterator;
   
3. 
   
4. //判断101-200之间有多少个素数，并输出所有素数。
   
5. 
   
6. public class Sushu
   
7. {
   
8.         public static void main(String[] args)
   
9.         {
   
10.                 ArrayList<Integer> al=getSuShu(2,200);//获得保存有所有小于200的素数的数组
    
11.                 //ArrayList<Integer> al=getSuShu2(2,200);//获得保存有所有小于200的素数的数组
    
12.                
    
13.                 System.out.println("给定范围内素数的个数为:"+al.size()+"个");
    
14.                 System.out.print("这些素数分别是:");
    
15.                 for(Iterator<Integer> it=al.iterator();it.hasNext();)
    
16.                 {
    
17.                         System.out.print(it.next()+" ");
    
18.                 }
    
19.         }
    
20.         private static ArrayList<Integer> getSuShu(int min,int max)//常规的遍历除
    
21.         {
    
22.                 ArrayList<Integer> al=new ArrayList<Integer>();
    
23.                
    
24.                 boolean flag=true;//标志是否为素数
    
25.                
    
26.                 if(min<=2)
    
27.                         al.add(2);
    
28.                
    
29.                 for(int i=(min%2==0?min+1:min);i<=max;i+=2)//素数除了2都不为偶数
    
30.                 {
    
31.                         flag=true;//初始化标识
    
32.                         for(int j=3;j<=Math.sqrt(i);j++)//因为已经排除了偶数所以可以不除2
    
33.                         {
    
34.                                 if(i%j==0)//只要能被整除就不是素数，跳出循环
    
35.                                 {
    
36.                                         flag=false;
    
37.                                         break;
    
38.                                 }
    
39.                         }
    
40.                         if(flag)
    
41.                                 al.add(i);//向集合添加素数
    
42.                 }
    
43.                
    
44.                 return al;
    
45.         }
    
46.        
    
47.         private static ArrayList<Integer> getSuShu2(int min,int max)//筛法
    
48.         {
    
49.                 ArrayList<Integer> al=new ArrayList<Integer>();//创建一个集合进行筛
    
50.                 ArrayList<Integer> al2=new ArrayList<Integer>();//保存筛出的素数
    
51.                
    
52.                 for(int i=2;i<max+1;i++)//初始化集合
    
53.                 {
    
54.                         al.add(i);
    
55.                 }
    
56.                
    
57.                 int a=0;//初始化除数
    
58.                 while(al.size()>0)//如果第一个集合内还有值就继续筛
    
59.                 {
    
60.                         a=al.get(0);//获得第一个集合中最小的数，这个数一定是素数
    
61.                         al2.add(a);//将这个素数加入集合2
    
62.                         for(int i=0;i<al.size();i++)//删除集合中这个数的倍数
    
63.                         {
    
64.                                 if(al.get(i)%a==0)
    
65.                                         al.remove(i);
    
66.                         }
    
67.                 }
    
68.                
    
69.                 for(int i=0;i<al2.size();i++)//遍历集合删除不符合范围的素数
    
70.                 {
    
71.                         if(al2.get(i)<min||al2.get(i)>max)
    
72.                                 al2.remove(i);
    
73.                 }
    
74.                
    
75.                 return al2;
    
76.         }
    
77. }

复制代码

zhaozhao 发表于 2014-12-14 12:15
请问你想要更简单的方法还是要效率更高的方法，如果想效率更高的话，可以i/2替换为Math.sqrt(i)! ...

这个可以。

冥夜 发表于 2014-12-14 13:50
这里给出了比较高效的求法，一个是常规的，一个是筛法。

牛b:hug:，受益了。

学习了！

冥夜 发表于 2014-12-14 13:50
这里给出了比较高效的求法，一个是常规的，一个是筛法。

筛法跟常规法在效率方面我觉得差不多，或者是我理解错了？:)

好吧，过来Mark一下！

Zomu_文林 发表于 2014-12-14 18:10
筛法跟常规法在效率方面我觉得差不多，或者是我理解错了？

理论上讲，数据量越大筛法优势越大，比如对于100，常规需要对100内的数每个都进行N次试除。而筛法每筛掉n个数，下一次需要进行判断的次数就减少了n次。也就是说常规是n*n次，筛法是n+(n-1)+（n-2）+...，这么讲明白了么

class Dome
{
        public static void main(String[] args)
        {
                man();
        }

        public static void man()
        {
                int[] arr=new int[188];
                arr[0]=3;//1和3就肯定的不判断了作为比较数了
                int num=1;
                for(int x=5;x<1000;x+=2)// 从5开始判断
                {
                        int sum=0;
                        for(int y=0;y<num;y++)//开始内循环 X和已经确认的质数的比较
                        {
                               
                                if(x%arr[y]!=0)//质数不能被其他质数整除
                                {
                                        sum++;//计数 作为有多少质数的依据
                                }
                        }
                        if(sum==num)
                        {
                                arr[num]=x;
                                num++;
                        }
                               
                }
                System.out.print("1"+","+"2"+",");
                for (int z=0;z<num;z++)
                {
                               
                        if(z==num-1)
                        {
                                System.out.print(arr[z]);
                        }
                        else
                        {
                                System.out.print(arr[z]+",");
                        }
                       
                }
        }
}

这是我的计算方式根据 质数只能被自身和1整除切都是奇数，重要一点质数不能被其他质数整除  虽然方法可能麻烦点。 不过感觉比较好懂  我也新学JAVA的

随风永夜 发表于 2014-12-14 18:38
class Dome
{
        public static void main(String[] args)

方法中的计数的就是质数个数 判断范围你可以设置成个变量  然后调用方法的时候作为参数

冥夜 发表于 2014-12-14 18:22
理论上讲，数据量越大筛法优势越大，比如对于100，常规需要对100内的数每个都进行N次试除。而筛法每筛掉n ...

噢，谢谢。。

Zomu_文林 发表于 2014-12-14 22:59
噢，谢谢。。

这个是对称根的问题，这哥们有点答非所问了。。。可以将时间复杂度大幅度减半。。

Rain2692 发表于 2014-12-14 23:02
这个是对称根的问题，这哥们有点答非所问了。。。可以将时间复杂度大幅度减半。。 ...

:D你们都是大神，那些后面的我都还没学，过段时间有问题在去请教你:hug:

随风永夜 发表于 2014-12-14 18:41
方法中的计数的就是质数个数 判断范围你可以设置成个变量  然后调用方法的时候作为参数 ...

嗯，不错，我也是刚学，加油！:hug:

冥夜 发表于 2014-12-14 13:50
这里给出了比较高效的求法，一个是常规的，一个是筛法。

遍历集合删除不符合范围的素数，这个步骤是否多余呢？
a1集合就这范围的数，怎么可能无形的产生超出范围的数呢？

as604049322 发表于 2014-12-17 07:27
遍历集合删除不符合范围的素数，这个步骤是否多余呢？
a1集合就这范围的数，怎么可能无形的产生超出范围 ...

因为筛法要从2、3、5这样的删，而且这些数是素数被取出来了，而题目要求100-200之间的素数，所以要去除- -不过的确有多余的部分，只要去除小于的部分就行了，大于的部分前面就有限制不会加进去

冥夜 发表于 2014-12-17 18:35
因为筛法要从2、3、5这样的删，而且这些数是素数被取出来了，而题目要求100-200之间的素数，所以要去除-  ...

不知道，添加前判断还是添加完成后再删哪个好，下面是我改 的代码
下面是我修改的代码：

1.     private static ArrayList<Integer> getPrimeNumList(int min,int max) {//筛法
   
2.         ArrayList<Integer> src=new ArrayList<Integer>();//创建一个集合进行筛
   
3.         ArrayList<Integer> result=new ArrayList<Integer>();//保存筛出的素数
   
4. 
   
5.         for(int i=2;i<=max;i++)//初始化集合
   
6.             src.add(i);
   
7. 
   
8.         int a=0;//初始化除数
   
9.         while(src.size()>0){//如果第一个集合内还有值就继续筛
   
10.             a=src.remove(0);//删除第一个集合中最小的数，这个数一定是素数
    
11.             if(a>=min)
    
12.                 result.add(a);//将这个素数加入集合2
    
13.             for(int i=0;i<src.size();i++){//删除集合中这个数的倍数
    
14.                 if(src.get(i)%a==0)
    
15.                     src.remove(i);
    
16.             }
    
17.         }
    
18.         return result;
    
19.     }

复制代码

as604049322 发表于 2014-12-17 19:47
不知道，添加前判断还是添加完成后再删哪个好，下面是我改 的代码
下面是我修改的代码：
...

嗯，你这样写更简洁一些。当时我就是看到了筛法的思路，所以就想把他做出来。然后没有进行优化就直接放上去了