打印一段数字中的所有质数的算法

痛定思痛。 2022-07-25 19:58 85阅读 0赞

简单实现如下。  
**算法一：**  
这个算法的中心思想是循环所有需要判断的数字，然后逐一进行取模判断。

public class IsPrime {
    
        public static void main(String[] args) {
            printPrimeNumber(3,100000);
        }
    
        public static void printPrimeNumber(int from, int to){
            Date d1 = new Date();
            if(to < from){
                System.out.println("参数错误");
                return;
            }
            System.out.println(from + "到" + to + "间的质数有：");
            boolean isPrime = true;
            for(int i = from; i <= to; i++){
                isPrime = true;
                for(int j = 2; j < i; j++){
                    if(i % j == 0){
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime)
                    System.out.print(i + " ");
            }
            Date d2 = new Date();
            System.out.println();
            System.out.println(d2.getTime()-d1.getTime());
        }
    }

**算法二**  
这个算法的中心思想是循环所有需要判断的数字，然后逐一进行取模判断。（取模判断的范围变小了，我们把i进行开方，因为所有能够被整除的数字一定小于它的开方）

public class IsPrime {
    
        public static void main(String[] args) {
            printPrimeNumber(3,100000);
        }
    
        public static void printPrimeNumber2(int from, int to){
            Date d1 = new Date();
            if(to < from){
                System.out.println("参数错误");
                return;
            }
            System.out.println(from + "到" + to + "间的质数有：");
            boolean isPrime = true;
            for(int i = from; i <= to; i++){
                isPrime = true;
                for(int j = 2; j <= Math.sqrt(i); j++){
                    if(i % j == 0){
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime)
                    System.out.print(i + " ");
            }
            Date d2 = new Date();
            System.out.println();
            System.out.println(d2.getTime()-d1.getTime());
        }
    }

算法二比算法一效率高了不少：  
算法一运行花费了：1514毫秒。  
算法二运行花费了：47毫秒。