Java 多方法实现素数判断并计算耗时

分类:Java 评论: 0

代码

package com.example.testbook;

public class PrimeNumber {
    public static void main(String[] args) {
        /**
         * min[int] and max[int] is target number range.
         */
        long st = System.currentTimeMillis(); // Start Time
        int min = 30;
        int max = 1000000;
        for (int i = min; i <= max; i++){
            isPrime3(i); // 修改调用方法,可以比较不同方法的效率差别
//            System.out.print(i + " ");
//            System.out.println(isPrime2(i));

        }
        long et = System.currentTimeMillis(); // End Time
        System.out.print("Program running cost time is: ");
        System.out.println(et - st + " ms");

    }

    /**
     * is Prime number method 1
     * @param n
     * @return
     */
    public static boolean isPrime1(int n){
        if (n <= 3) {
            return n > 1;
        }
        for (int i = 2; i < n; i++){
            if (n % i == 0){
                return false;
            }
        }
        return true;
    }

    /**
     * is Prime number method 2
     * @param n
     * @return
     */
    public static boolean isPrime2(int n){
        if (n <= 3){
            return n > 1;
        }
        int sqrt = (int)Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++){
            if (n % i == 0){
                return false;
            }
        }
        return true;
    }
     /**
     * is Prime number method 3
     * @param n
     * @return
     */
    public static boolean isPrime3(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

附录

参考链接

回复