黑马程序员技术交流社区
标题: 【2个技术分哦】王震阳老师第11期测试题思路分享 [打印本页]
作者: 沿途小将 时间: 2014-8-15 18:17
标题: 【2个技术分哦】王震阳老师第11期测试题思路分享
本帖最后由 沿途小将 于 2014-8-15 18:31 编辑
试题链接：王老师11期技术分题目
活动目的：练习javaSE知识。
活动奖励：最高2个技术分
结束时间：2014年8月18日，过期提交可能获取不到技术分！
代码提交要求：将自己的源代码压缩然后提交，提交的时候设置为管理员权限，以其他方式提交的答案无效。上交源码的时候不需要将整个工程项目压缩，只需将用到的源文件压缩即可。
题目类型：JavaSE 算法题。
难易程度：容易
这题不会太难，只是有个技巧，可以让代码更少些（纯属个人认为，莫见怪！）。
思路：这是一个求一段数中的所有质数。而且提示了质数有两个特点（只能被1和自己整除），所有我可以用for循环（循环语句都可）让这个数（假设为X）对1到他自己（X）取余，余数等于零则可整除。当余数等于零的个数为二时，该数为质数。其他的为细节，如X的取值范围啦。
我的代码如下：
- import java.util.*;
- public class Test11 {
- int shu = 0;
- public static void main(String[] args) {
- new Test11().GetPrime();
- }
- public Test11() {
- System.out.println("请输入一个大于1且小于500的整数");
- Scanner sc = new Scanner(System.in);
- shu = sc.nextInt();
- }
- public void GetPrime() {
- if (shu < 500 && shu > 1) {
- for (int i = 1; i <= shu; i++) {
- int time = 0;
- for (int j = 1; j <= i; j++) {
- if ((i % j) == 0) {
- time++;
- }
- }
- if (time == 2) {
- System.out.println(i);
- }
- }
- } else {
- System.out.println("你输入的数不合要求！");
- }
- }
- }
有误处，请多指正！
作者: 左脑想你 时间: 2014-8-15 22:23
改进，判断输入的是否符合要求然后让重新输入
作者: 男人你得有范 时间: 2014-8-15 22:31
先来踩一下，回头好好看看
作者: fantacyleo 时间: 2014-8-15 22:49
太麻烦了：
1. 没有必要统计余数等于零的个数
2. 没有必要让X对1到他自己（X）取余
判断一个自然数是否质数，只需要：
- boolean isPrime(int n) {
- if (n == 1) // 1不是质数
- return false;
- if (n <= 3) // 2、3是质数
- return true;
- for (int i = 2; i * i <= n; i++) { // 对于其余的n，只要无法被每一个平方不大于n的数整除，n就是质数
- if (n % i == 0)
- return false; // 只要能被某一个平方不大于n的数整除，n就不是质数
- }
- return true;
-
- }
打印某一范围内的质数
- void primesInRange(int begin, int end) {
- for (int i = begin; i <= end; i++) {
- if (isPrime(i)) // 如果i是质数，则打印
- System.out.println(i);
- }
- }
作者: 明天2014 时间: 2014-8-16 02:15
:o楼主你这方法效率虽然不高，但是够直接。。。赞一个。。。
我参考你的搞了个麻烦的，据说能提高效率，有兴趣的大家可以一起探讨下。
- import java.util.*;
- public class PrimeNumberTest
- {
- public static void main(String[] args)
- {
- int num;
- System.out.println("请输入一个大于1且小于500的整数");
- Scanner sc = new Scanner(System.in);
- num = sc.nextInt();
- while(num<=1||num>=500)
- {
- System.out.println("你输入的数不合要求!");
- return;
- }
- getPrime(num);
- }
- public static void getPrime(int num)
- {
- int []arr=new int [255];
- int pc=1,m=3,k=0;
- arr[0]=2;
- while(m<=num)
- {
- while(arr[k]*arr[k]<=m)
- if(m%arr[k]==0)
- {/*m是合数*/
- m+=2;/*让m取下一个奇数*/
- k=1;/*不必用primes[0]=2去测试m，所以k从一开始*/
- }
- else
- k++;/*继续用下一个质数去测试*/
- if(m>num) break;
- arr[pc++]=m;
- m+=2;/*除2外，其余质数均是奇数*/
- k=1;
- }
- /*输出primes[0]至primes[pc-1]*/
- for(k=0;k<pc;k++)
- System.out.print(arr[k]+" ");
- }
- }
作者: 沿途小将 时间: 2014-8-16 07:50
你这个想法也可以，但是还得设一个“退出”的选项，我这不合要求就直接程序执行完了
作者: 沿途小将 时间: 2014-8-16 07:55
本帖最后由 沿途小将 于 2014-8-16 07:57 编辑
范围1<X<500
作者: 沿途小将 时间: 2014-8-16 07:56
本帖最后由 沿途小将 于 2014-8-16 08:01 编辑
你的while()；没什么用，你仔细看下。另：你和楼上的是师兄弟吗？方法是一样的。:lol
作者: 明天2014 时间: 2014-8-16 10:46
:o不是吧？你确定你说的是我的？我没看到有人跟我用一样的方法啊。。。
我在原来的判断基础上做了3点改进：
1.偶数没有必要判断，自然也没有必要对2取余。（当然2除外，2可以单独判断）。
2.取余范围不用1~N，1到N开2次方就可以了。
3.因为合数肯定可以分解成质数和另一个数的乘积。所以判断取余的时候，只对质数取余即可。
如：121 只需对3,5,7,11这几个数进行取余判断即可。。。9不用判断，因为9是合数。（第三点排除的）
作者: fantacyleo 时间: 2014-8-16 10:54
沿途小将 发表于 2014-8-16 07:55
范围1
这无关紧要
作者: 沿途小将 时间: 2014-8-16 11:12
例如；num=600;他还是会执行方法getPrime();
作者: 沿途小将 时间: 2014-8-16 11:14
这个思路，确实是能提高很多，我该向你学习
作者: 嘿～～ 时间: 2014-8-16 11:17
直接给内外循环加标记，我自己做的，比这个代码少多了
作者: 沿途小将 时间: 2014-8-16 11:25
也是，受教了:)
作者: 沿途小将 时间: 2014-8-16 11:27
:):):handshake:handshake
作者: 沿途小将 时间: 2014-8-16 11:28
怎么个标记法？
作者: 嘿～～ 时间: 2014-8-16 11:41
W:for (; ; )//W是外层循环标记
{
Q:for (; ; )//Q是外层循环标记
{
break Q;//表示在此处中断内层循环
break W;//表示在此处中断外层循环
//也可以用continue,
//以上语句可以定义在循环体的任何地方
}
}
作者: 沿途小将 时间: 2014-8-16 11:53
那我只能:lol:lol
作者: 王凯路路 时间: 2014-8-16 12:33
大神果然很多啊.
作者: justin1258 时间: 2014-8-16 20:13
还有改进的余地，可以参考这个：http://blog.csdn.net/program_think/article/details/7032600/
作者: fantacyleo 时间: 2014-8-16 22:27
嗯嗯，进一步优化必然要上数论了。
作者: 李国荧 时间: 2014-8-17 07:29
学习一下……
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |