java高效算法求整数n中的所有素数

该算法比较高效,求1亿内所有素数也仅为2秒左右,依据是所有的合数都可以拆分为:n * m ,而质数只能被1和其本身整除。

/**
 * 求0-num 所有质数
 * @author https://www.lanhong-vip.com/
 * @date 2020-12-19
 */
public class GetPrimeByNum {

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int num = 100000000;
        byte[] list = new byte[num + 1];
        //0与1不是质数,排除,置为-1,byte数组默认各元素值为0
        list[0] = list[1] = -1;
        for (int i = 2; i <= num; i++) {
            if (list[i] == 0) {
                //任意合数都有除1和本身能整除其的数
                for (int j = i * 2; j <= num; j += i) {
                    //是合数将其值修改成-1
                    list[j] = -1;
                }
            }
        }
        int count = 0;
        //计算质数的数量,为0的都是质数
        for (int i = 1; i < num; i++) {
            if (list[i] == 0) count++;
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime) + "毫秒,个数:" + count);
    }
}




分享到: 新浪微博 微信 QQ好友 QQ空间 豆瓣

相关文章

发表评论

电子邮件地址不会被公开。




Enter Captcha Here :