java高效求解素数算法

素数算法测试

1、求解0~n之间的所有素数，测试了网上几种常见的素数算法，经测试发现该算法是求解效率最好的，不过具体实现思路未深入研究

/**
 * 说明： 素数测试
 * 
 * @version 1.0
 * @author me@longlonggo.com
 *
 */
public class PrimeNumberTest {

    public static void main(String[] args) {
        long t = System.currentTimeMillis();
        
        //10000000(别数了1千万)内，素数有664579个，查找用时2185毫秒
        int maxNum = 10000000;
        testSushu(maxNum);
        long diff = System.currentTimeMillis() - t;
        System.out.println("计算用时【" + diff + "】毫秒");
    }

    /**
     * @Title testSushu
     * @Description 比1大的整数中,除了1和它本身以外,不再有别的因数,这种整数叫做质数或素数
     * @param maxNum 最大值范围
     */
    private static void testSushu(int maxNum) {
        boolean[] primes = new boolean[maxNum + 1]; // 质数数组

        // 初始化所有数字为true
        for (int i = 0; i < primes.length; i++) {
            primes[i] = true;
        }

        //筛法主要的思路是:
        //对于这么多数，如果一个数是素数的倍数，那么那个数肯定不是素数。
        //所以从k=2开始，将数组中2的倍数（不包括2）的布尔值改为false，代表它们不是素数，
        //然后k=3，进行一次筛选,k=5，进行一次筛选。。。。
        //一直遍历到k的平方根为止，剩下的留在数组中的数就是素数
        for (int k = 2; k <= maxNum / k; k++) {
            if (primes[k]) {
                for (int i = k; i <= maxNum / k; i++) {
                    primes[k * i] = false; // k * i is not prime
                }
            }
        }

        final int NUMBER_PER_LINE = 10; // 一行显示10个数字
        int count = 0; // 到目前为止找到的质数数量
        // 打印质数
        for (int i = 2; i < primes.length; i++) {
            if (primes[i]) {
                count++;
                if (count % NUMBER_PER_LINE == 0)
                    System.out.printf("%8dn", i);
                else
                    System.out.printf("%8d", i);
            }
        }
        System.out.println("n质数数量【" + count + "】个");
    }
}

注：

    本文样例代码参考：https://blog.csdn.net/yeya24/article/details/80157740