image.png
    image.png
    核心：每一个合数都能被小于他的质数分解掉
    代码一步步优化：

    1.    public static void main(String[] args) {
    2.         System.out.println(eratosthenes2(100));
    3.     }
    5.     public static int process(int n ){
    6.         return -1;
    7.     }
    8.     public static int eratosthenes2( int n ){
    9.         /**标记位，是否位合数*/
    10.         boolean[] flag = new boolean[n+1];
    11.         int count = 0;
    12.         for( int i = 2; i <= n ; i++){
    13.             if(flag[i])continue;;
    14.             /**把这个判断去掉才是埃筛法的真谛，所有小于他的数在进行倍增的时候，已经把小于当前数的合数给过滤掉了*/
    15.             //if(isPrime(i)){
    16.             /**倍增过滤掉*/
    17.             count++;
    18.             /**另一种写法，用加法递增取代乘法。*/
    19.             for(int j = i*i ; j<=n; j+=i){
    20.              flag[j] = true;
    21.              }
    22.             //}
    23.         }
    24.         return count;
    25.     }
    26.     /**素数，非素数-合数
    27.      * 发现一个素数的时候，进行倍增*/
    28.     public static int eratosthenes( int n ){
    29.         /**标记位，是否位合数*/
    30.         boolean[] flag = new boolean[n+1];
    31.         int count = 0;
    32.         for( int i = 2; i <= n ; i++){
    33.             if(flag[i])continue;;
    34.             /**把这个判断去掉才是埃筛法的真谛，所有小于他的数在进行倍增的时候，已经把小于当前数的合数给过滤掉了*/
    35.             //if(isPrime(i)){
    36.                 /**倍增过滤掉*/
    37.                 count++;
    38.                 for(int j = i; i*j<=n; j++){
    39.                     flag[i*j] = true;
    40.                 }
    41.                 /**另一种写法，用加法递增取代乘法。*/
    42.                 /**for(int j = 2*i ; j<=n; j+=i){
    43.                     flag[j] = true;
    44.                 }*/
    45.             //}
    46.         }
    47.         return count;
    48.     }
    49.     public static boolean isPrime(int n ){
    50.         for(int i = 2; i * i <=n; i++){
    51.             if(n%i == 0){
    52.                 return false;
    53.             }
    54.         }
    55.         return true;
    56.     }

    关于复杂度：看看就行了。
    image.png
    为什么埃式筛法的时间复杂度是O(nloglogn)？ - 知乎 https://www.zhihu.com/question/35112789