这个质数生成器在几个星期前就完成了，只不过那时没有创建这个博客，那么就以此作为这个博客的第一篇正式的文章。

质数验证部分

这一部分是整个程序的核心。

程序完成任务所需的时间在不同性能的电脑上不同，此部分中所有的数据是在我自己的电脑上得出来的。

第一版

java


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; 语句

第二版

java


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 分钟。

第三版和第四版

更新太少直接合并在一起

java


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 秒左右。

第五版

java


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 秒。

封装

完整的程序

我没有制作任何图形化的功能。
代码中有注释，我就不再解释了。
(代码框左侧按钮可以将代码收起，如果太多的话。右侧按钮可以直接复制)

java


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即为合数

java


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;
    }
}