试题链接：王老师11期技术分题目

活动目的：练习javaSE知识。

活动奖励：最高2个技术分

结束时间：2014年8月18日，过期提交可能获取不到技术分！

代码提交要求：将自己的源代码压缩然后提交，提交的时候设置为管理员权限，以其他方式提交的答案无效。上交源码的时候不需要将整个工程项目压缩，只需将用到的源文件压缩即可。

题目类型：JavaSE 算法题。

难易程度：容易

这题不会太难，只是有个技巧，可以让代码更少些（纯属个人认为，莫见怪！）。

思路：这是一个求一段数中的所有质数。而且提示了质数有两个特点（只能被1和自己整除），所有我可以用for循环（循环语句都可）让这个数（假设为X）对1到他自己（X）取余，余数等于零则可整除。当余数等于零的个数为二时，该数为质数。其他的为细节，如X的取值范围啦。

我的代码如下：

1. import java.util.*;
   
2. 
   
3. public class Test11 {
   
4.         int shu = 0;
   
5. 
   
6.         public static void main(String[] args) {
   
7.                 new Test11().GetPrime();
   
8.         }
   
9. 
   
10.         public Test11() {
    
11.                 System.out.println("请输入一个大于1且小于500的整数");
    
12.                 Scanner sc = new Scanner(System.in);
    
13.                 shu = sc.nextInt();
    
14.         }
    
15. 
    
16.         public void GetPrime() {
    
17.                 if (shu < 500 && shu > 1) {
    
18.                         for (int i = 1; i <= shu; i++) {
    
19.                                 int time = 0;
    
20.                                 for (int j = 1; j <= i; j++) {
    
21. 
    
22.                                         if ((i % j) == 0) {
    
23.                                                 time++;
    
24.                                         }
    
25. 
    
26.                                 }
    
27.                                 if (time == 2) {
    
28.                                         System.out.println(i);
    
29.                                 }
    
30. 
    
31.                         }
    
32.                 } else {
    
33.                         System.out.println("你输入的数不合要求！");
    
34.                 }
    
35.         }
    
36. }
    

复制代码

有误处，请多指正！

改进，判断输入的是否符合要求然后让重新输入

先来踩一下，回头好好看看

太麻烦了：
1. 没有必要统计余数等于零的个数
2. 没有必要让X对1到他自己（X）取余

判断一个自然数是否质数，只需要：

1. boolean isPrime(int n) {
   
2.     if (n == 1) // 1不是质数
   
3.         return false;
   
4.     if (n <= 3) // 2、3是质数
   
5.         return true;
   
6.     for (int i = 2; i * i <= n; i++) { // 对于其余的n，只要无法被每一个平方不大于n的数整除，n就是质数
   
7.         if (n % i == 0)
   
8.             return false; // 只要能被某一个平方不大于n的数整除，n就不是质数
   
9.     }
   
10.     return true;
    
11.      
    
12. }

复制代码

打印某一范围内的质数

1. void primesInRange(int begin, int end) {
   
2.     for (int i = begin; i <= end; i++) {
   
3.         if (isPrime(i)) // 如果i是质数，则打印
   
4.             System.out.println(i);
   
5.     }
   
6. }

复制代码

:o楼主你这方法效率虽然不高，但是够直接。。。赞一个。。。
我参考你的搞了个麻烦的，据说能提高效率，有兴趣的大家可以一起探讨下。

1. import java.util.*;
   
2. public class PrimeNumberTest
   
3. {
   
4.         public static void main(String[] args)
   
5.         {
   
6.                 int num;
   
7.                 System.out.println("请输入一个大于1且小于500的整数");
   
8.                 Scanner sc = new Scanner(System.in);
   
9.         num = sc.nextInt();
   
10.                 while(num<=1||num>=500)
    
11.                 {
    
12.                         System.out.println("你输入的数不合要求!");
    
13.                         return;
    
14.                 }
    
15.                 getPrime(num);
    
16.         }
    
17.         public static void getPrime(int num)
    
18.         {
    
19.                 int []arr=new int [255];
    
20.                 int pc=1,m=3,k=0;
    
21.                 arr[0]=2;
    
22.                 while(m<=num)
    
23.                 {
    
24.                         while(arr[k]*arr[k]<=m)
    
25.                                 if(m%arr[k]==0)
    
26.                                 {/*m是合数*/
    
27.                                         m+=2;/*让m取下一个奇数*/
    
28.                                         k=1;/*不必用primes[0]=2去测试m，所以k从一开始*/
    
29.                                 }
    
30.                                 else
    
31.                                 k++;/*继续用下一个质数去测试*/
    
32.                         if(m>num) break;
    
33.                         arr[pc++]=m;
    
34.                         m+=2;/*除2外，其余质数均是奇数*/
    
35.                         k=1;
    
36.                 }
    
37.                 /*输出primes[0]至primes[pc-1]*/
    
38.                 for(k=0;k<pc;k++)
    
39.                         System.out.print(arr[k]+" ");               
    
40.         }
    
41. }
    

复制代码

左脑想你 发表于 2014-8-15 22:23
改进，判断输入的是否符合要求然后让重新输入

你这个想法也可以，但是还得设一个“退出”的选项，我这不合要求就直接程序执行完了

fantacyleo 发表于 2014-8-15 22:49
太麻烦了：
1. 没有必要统计余数等于零的个数
2. 没有必要让X对1到他自己（X）取余

范围1<X<500

明天2014 发表于 2014-8-16 02:15
楼主你这方法效率虽然不高，但是够直接。。。赞一个。。。
我参考你的搞了个麻烦的，据说能提高效率，有 ...

你的while()；没什么用，你仔细看下。另：你和楼上的是师兄弟吗？方法是一样的。:lol

沿途小将 发表于 2014-8-16 07:56
你的while()；没什么用，你仔细看下。另：你和楼上的是师兄弟吗？方法是一样的。 ...

:o不是吧？你确定你说的是我的？我没看到有人跟我用一样的方法啊。。。
我在原来的判断基础上做了3点改进：
1.偶数没有必要判断，自然也没有必要对2取余。（当然2除外，2可以单独判断）。
2.取余范围不用1~N，1到N开2次方就可以了。
3.因为合数肯定可以分解成质数和另一个数的乘积。所以判断取余的时候，只对质数取余即可。
如：121  只需对3,5,7,11这几个数进行取余判断即可。。。9不用判断，因为9是合数。（第三点排除的）

沿途小将 发表于 2014-8-16 07:55
范围1

这无关紧要

沿途小将 发表于 2014-8-16 07:56
你的while()；没什么用，你仔细看下。另：你和楼上的是师兄弟吗？方法是一样的。 ...

例如；num=600;他还是会执行方法getPrime();

明天2014 发表于 2014-8-16 10:46
不是吧？你确定你说的是我的？我没看到有人跟我用一样的方法啊。。。
我在原来的判断基础上做了3点改进 ...

这个思路，确实是能提高很多，我该向你学习

直接给内外循环加标记，我自己做的，比这个代码少多了

fantacyleo 发表于 2014-8-16 10:54
这无关紧要

也是，受教了:)

沿途小将 发表于 2014-8-16 11:14
这个思路，确实是能提高很多，我该向你学习

:):):handshake:handshake

嘿～～ 发表于 2014-8-16 11:17
直接给内外循环加标记，我自己做的，比这个代码少多了

怎么个标记法？

沿途小将 发表于 2014-8-16 11:28
怎么个标记法？

W:for (; ; )//W是外层循环标记
{
        Q:for (; ; )//Q是外层循环标记
        {
                break Q;//表示在此处中断内层循环
                break W;//表示在此处中断外层循环
                //也可以用continue,
                //以上语句可以定义在循环体的任何地方
        }
}

嘿～～ 发表于 2014-8-16 11:41
W:for (; ; )//W是外层循环标记
{
        Q:for (; ; )//Q是外层循环标记

那我只能:lol:lol

大神果然很多啊.

fantacyleo 发表于 2014-8-15 22:49
太麻烦了：
1. 没有必要统计余数等于零的个数
2. 没有必要让X对1到他自己（X）取余

还有改进的余地，可以参考这个：http://blog.csdn.net/program_think/article/details/7032600/