java 孪生素数几种算法

1. 普通方法

public static boolean isPrime1(int x) {
        for (int i = 2; i <= x / 2; i++) {
            if (x % i == 0) { // 能被整除则不为素数
                return false;
            }
        }
        return true;
    }

2. 一般优化方法

public static boolean isPrime2(int n) {
        if (n < 2) {
            return false;
        }
        int k = (int) Math.sqrt(n) + 1;
        for (int i = 2; i < k; ++i) {
            if (0 == n % i) {
                return false;
            }
        }
        return true;
    }
 

3. 六素数法  -- 详见百度百科

在数学中，六素数（sexy prime）是相差为 6 的素数偶 (p, p + 6)。例如数 5 和 11 都是素数且差为 6。如果 p + 2 或 p + 4 也是素数，则六素数是素数三元组的一部分
首先解释一下什么叫六素数。六素数的英文为 “sexy prime” ，是相差为6的素数偶( p , p + 6 )，500之下的六素数 有： 
(5,11), (7,13), (11,17), (13,19), (17,23), (23,29), (31,37), (37,43), (41,47), (47,53), (53,59), (61,67), (67,73), (73,79), (83,89), (97,103), (101,107), (103,109), (107,113), (131,137), (151,157), (157,163), (167,173), (173,179), (191,197)

// 第三种方法
    public static boolean isPrime3(int n) {
        if (n <= 3) {
            return n > 1;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
    
        int k = (int) Math.sqrt(n) + 1;
        for (int i = 5; i < k; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

整个类方法代码:

import java.util.Scanner;

public class TwinPrimeNumDemo {
    public static void main(String[] args) {
        System.out.println("begin");
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n < 1 || n > 100000001) {
                break;
            }
            long begin = System.currentTimeMillis();
            System.out.println(n + " *1=" + twinPrimeNum(n, 1));
            long end = System.currentTimeMillis();
            System.out.println("1 time = " + (end - begin));

            System.out.println(n + " *2=" + twinPrimeNum(n, 2));
            long end1 = System.currentTimeMillis();
            System.out.println("2 time = " + (end1 - end));

            System.out.println(n + " *3=" + twinPrimeNum(n, 3));
            long end2 = System.currentTimeMillis();
            System.out.println("3 time = " + (end2 - end1));
        }
        sc.close();
        System.out.println("end");
    }

    // 判断相邻的且距离为：2 的两个素数
    public static int twinPrimeNum(int n, int type) {
        int sum = 0;
        // 累加次数
        if (type == 1) {
            for (int i = 2; i < n; i++) // 最小的素数是：2
            {
                if (isPrime1(i) && isPrime1(i + 2))
                    sum++; // 在目标值内寻找孪生素数
            }
        }
        else if (type == 2) {
            for (int i = 2; i < n; i++) // 最小的素数是：2
            {
                if (isPrime2(i) && isPrime2(i + 2))
                    sum++; // 在目标值内寻找孪生素数
            }
        }
        else if (type == 3) {
            for (int i = 2; i < n; i++) // 最小的素数是：2
            {
                if (isPrime3(i) && isPrime3(i + 2))
                    sum++; // 在目标值内寻找孪生素数
            }
        }

        return sum;
        // 返回最后的组数
    }

    // 第一种方法：判断是否是素数
    public static boolean isPrime1(int x) {
        for (int i = 2; i <= x / 2; i++) {
            if (x % i == 0) { // 能被整除则不为素数
                return false;
            }
        }
        return true;
    }

    // 第二种方法

public static boolean isPrime2(int n) {
        if (n < 2) {
            return false;
        }
        int k = (int) Math.sqrt(n) + 1;
        for (int i = 2; i < k; ++i) {
            if (0 == n % i) {
                return false;
            }
        }
        return true;
    }

    // 第三种方法
    public static boolean isPrime3(int n) {
        if (n <= 3) {
            return n > 1;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
    
        int k = (int) Math.sqrt(n) + 1;
        for (int i = 5; i < k; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}

 

输出结果对比：