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);
}
}
判断十亿以内素数的个数