这个质数生成器在几个星期前就完成了,只不过那时没有创建这个博客,那么就以此作为这个博客的第一篇正式的文章。
质数验证部分
这一部分是整个程序的核心。
程序完成任务所需的时间在不同性能的电脑上不同,此部分中所有的数据是在我自己的电脑上得出来的。
第一版
for(;num1<=num2;num1 ++){ int count = 0; if(num1 == 1){ }else if(num1 == 2){ System.out.println(num1); }else{ for(int j = (num1-1);j != 1;j--){ if(num1 % j != 0){ count ++; } } if((num1 - 2 ) == count){ System.out.println(num1); } }}
第一行的 for 循环用来生成指定范围内的所有数字来给下面的部分计算,num1 和 num2 就是指定范围的数。因为 num1<=num2 这个判断语句,所以在输入的时候 num1 必须大于或等于 num2。当然,也可以在这个程序前面加上一个判断语句,自动将大的数赋值给 num2,小的数赋值给 num1。
第三行开始的if语句用于排除特殊情况。
第七行的 for 从大到小生成数字和num1求余。也正因为这样设计,导致程序效率底下,在我自己的电脑上花了4分钟多才计算出 1-100000 中所有的质数。
第二行的 int 用来初始化计数器,第十二行的 if 则是判断每次求余之后是否都不为 0。同样这种设计导致程序效率再度下降。
此时我还没学习到 break; 语句
第二版
for(;num1<=num2;num1 ++){ boolean isIt = true; switch (num1) { case 1: break; case 2: System.out.println(num1); break; default: for(int j = ((num1 / 2) + 1);j != 1;j--){ if(num1 % j == 0){ isIt = false; break; } } if(isIt){ System.out.println(num1); } }}
这一次把 if 判断换成了 switch 来判断。同样还是排除特殊的数字。
第十行判断非特殊数字只需要判断原先的一半,效率提升了不少。
删除了计数器,改用 boolean 来判断是否为质数,使得效率有细微的提升。
此时学到了 break; 这样一旦发现求余为 0 就不用继续判断,效率提升。
这次计算 1-100000 花了约 1 分钟。
第三版和第四版
更新太少直接合并在一起
for(;num1<=num2;num1 ++){ boolean isIt = true; switch (num1) { case 1: break; case 2: System.out.println(num1); break; default: for(int j = 2;j <= Math.sqrt(num1);j++){ if(num1 % j == 0){ isIt = false; break; } } if(isIt){ System.out.println(num1); } }}
只更新了第十行,j-- 变为j++,可以快速排除掉 2 以外的偶数。并且最大只计算到 根号num1 ,再次减少计算量。java中小数转整数默认向下取整,这不影响正常计算。
这次计算 1-100000 内所有质数花了 10 秒左右。
第五版
for(;num1<=num2;num1 ++){ isIt = true; switch (num1) { case 1: break; case 2: System.out.println(num1); break; default: int j2 = (int)Math.sqrt(num1); for(int j = 2;j <= j2;j++){ if(num1 % j == 0){ isIt = false; break; } } if(isIt){ System.out.println(num1); } }}
第二行考虑到每循环一次就开辟一次会耗费时间,自己测试了一下,发现开辟空间比修改数值花的时间多(尽管只多了一点点),但还是让 isIt 在循环外先创建好。
以此类推,原本第十行每判断一次就要开一次方,不如提前开方好,效果很不错。
计算 1-100000 内所有的质数只花了 1 秒。
封装
完整的程序
我没有制作任何图形化的功能。
代码中有注释,我就不再解释了。
(代码框左侧按钮可以将代码收起,如果太多的话。右侧按钮可以直接复制)
public class OT2 { public static void main(String[] args) { //程序初始化 java.util.Scanner s = new java.util.Scanner(System.in); boolean isIt = true; int num2; System.out.println("欢迎使用质数生成器" + '\n'); System.out.println("此质数生成器会遍历指定范围内的所有数字" + '\n' + "计算量随范围和数字增大而增大" + '\n' + "量算力而行,按下 Ctrl + C 可关闭程序"); //用户控制和输入 for(;;){ System.out.println('\n' + "只能输入数字,且第一个数字要小于或等于第二个数字" + '\n'); //当最大数字到达2147483647时,会出现错误的负数输出,目前只能向下限制 System.out.println("输入范围(1 ~ 2147483646):"); int num1 = s.nextInt(); //检查num1输入合法性 if(num1 <1){ System.out.println("\n" + num1 + " 太小,请重新输入"); continue; }else if(num1 > 2147483646){ System.out.println("\n" + num1 + " 太大,请重新输入"); continue; } //num2输入 for(;;){ System.out.println("到"); num2 = s.nextInt(); //检查num2合法性 if(num2 < num1){ System.out.println("\n" + num2 + "比" + num1 + "小,请重新输入"); continue; }else if(num2 > 2147483646){ System.out.println("\n" + num2 + " 太大,请重新输入"); continue; //检查完成,退出循环 }else{ break; } } //输出区分隔 System.out.println('\n' + "计算结果:" + '\n'); //计算和输出 for(;num1<=num2;num1 ++){ //恢复检测情况 isIt = true; //排除特殊情况 switch (num1) { case 1: break; case 2: System.out.println(num1); break; //计算非特殊情况(原:除以每个比它小的所有数(1除外);优化:除以比它一半小的所有数(1除外)) default: //优化,从小到大求余比从大到小快1倍 //for(int j = ((num1 / 2) + 1);j != 1;j--){ //for(int j = 2;j <= ((num1 / 2) + 1);j++){ //for(int j = 2;j < (num1 / 2);j++){ //for(int j = 2;j <= sqrt(num1);j++){ //优化,使用根号运算,减少运算量(数值较大时较为明显) //for(int j = 2;j <= Math.sqrt(num1);j++){ //优化,平方只计算一次 int j2 = (int)Math.sqrt(num1); for(int j = 2;j <= j2;j++){ //验证计算:求余为0则不计算 if(num1 % j == 0){ isIt = false; break; } } //验证是否每次求余都不为0 if(isIt){ //打印输出 System.out.println(num1); } } } } }}
模块形式
学了java中的方法之后,我将其做成一个模块,方便调用。
调用的代码:primeNumberCalculation.primeNumberCalculation(num1)
num1是要检测的数值,范围在1~2147483646,类型为int
程序会返回boolean类型的值,true即为质数,false即为合数
public class primeNumberCalculation { public static boolean primeNumberCalculation(int num1){ switch(num1){ //排除特殊情况 case 1: return false; case 2: return true; //计算非特殊情况 default : //生成范围内的数提供计算 int j2 = (int)Math.sqrt(num1); int j = 2; for(j = 2;j <= j2;j++){ //验证计算:求余为0则不计算并返回false if(num1 % j == 0){ return false; } } } //通过计算,返回true return true; }}