这个质数生成器在几个星期前就完成了，只不过那时没有创建这个博客，那么就以此作为这个博客的第一篇正式的文章。
质数验证部分
这一部分是整个程序的核心。
程序完成任务所需的时间在不同性能的电脑上不同，此部分中所有的数据是在我自己的电脑上得出来的。
第一版
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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。同样这种设计导致程序效率再度下降。
第二版
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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 分钟。
第三版和第四版
更新太少直接合并在一起
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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 秒左右。
第五版
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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 秒。
封装
完整的程序
我没有制作任何图形化的功能。
代码中有注释，我就不再解释了。
(代码框左侧按钮可以将代码收起，如果太多的话。右侧按钮可以直接复制)
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| 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');
System.out.println("输入范围（1 ~ 2147483646）：");
int num1 = s.nextInt();
if(num1 <1){
System.out.println("\n" + num1 + " 太小，请重新输入");
continue;
}else if(num1 > 2147483646){
System.out.println("\n" + num1 + " 太大，请重新输入");
continue;
}
for(;;){
System.out.println("到");
num2 = s.nextInt();
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;
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);
}
}
}
}
}
}
|
模块形式
学了java中的方法之后，我将其做成一个模块，方便调用。
调用的代码：
primeNumberCalculation.primeNumberCalculation(num1)
num1是要检测的数值，范围在1~2147483646，类型为int
程序会返回boolean类型的值，true即为质数，false即为合数
java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 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++){
if(num1 % j == 0){
return false;
}
}
}
return true;
}
}
|