判断十亿以内素数的个数

import java.util.ArrayList;
import java.util.List;
//算法原理:从2开始,将[2, 根号n]中每个素数当作最小质因数去标记合数,剩下的就都是素数。(对比埃氏筛法理解)
//时间复杂度:O(n)
/*
  算法中break那行代码的原理最难理解,作用就是弥补埃氏筛法的不足,防止重复筛除合数。

  代码含义:如果当前素数primes.get(j)是数字i的最小质因数,那么后面的素数就不可能是数字i及其倍数的最小质因数。

  举个例子:假如当前数字是8,当前素数是2,理应跳出循环。如果继续,那么下一个素数是3,所以8*3=24 ,但是24的最小质因数是2不是3,再继续8*4=32 ,32的最小质因数是2不是5,以此类推,可以发现8及其倍数的最小质因数都应该是2,所以到2这里就应该跳出循环了。
*/
public class Primes {
    public static List<Integer> getPrimes(int num){
        List<Integer> list = new ArrayList<>();
        if(num == 0 || num == 1){
            return list;
        }
        boolean[] tags = new boolean[num+1];
        //true代表不是素数
        tags[0] = true;
        tags[1] = true;
        for(int i = 2; i <= num;i++){
            if(!tags[i]){
                list.add(i);
            }
            for(int j = 0; j < list.size() && i * list.get(j) <= num; j++){
                tags[i * list.get(j)] = true;
                if(i % list.get(j) == 0){
                    break;
                }
            }
        }
        System.out.println(list.size());
        return list;
    }

    public static void main(String[] args) {
        List<Integer> primes = getPrimes(1000000000);
        System.out.println(primes);
    }
}

判断十亿以内素数的个数

上一篇:监听页面路径


下一篇:[字符串入门]最小表示法