当前位置: 首页 >> Java >> java高效求解素数算法 >> 正文

java高效求解素数算法

11个月前 (09-26)     作者:4869     分类:Java     阅读次数:2127     评论(0)    文章页统计代码

素数算法测试

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("%8d\n", i);
                else
                    System.out.printf("%8d", i);
            }
        }
        System.out.println("\n质数数量【" + count + "】个");
    }
}

注:

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

除非注明,发表在“石马人山的博客”的文章『java高效求解素数算法』版权归4869所有。 转载请注明出处为“本文转载于『石马人山的博客』原地址http://longlonggo.com/post/409.html
文章页分享代码

评论

发表评论   

昵称*

E-mail*(建议输入,以便收到博主回复的提示邮件)

网站