埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
------援引自百度百科
算法思想：要得到自然数n以内的全部素数，必须把不大于
的所有素数的倍数剔除，剩下的就是素数。
public int countPrimes(int n) { if (n <= 2){ return 0; } int count = 0; boolean[] isS = new boolean[n + 1]; for (int i = 2; i < n; i++) { if (isS[i]){ continue; } count++; for (int j = 1; j * i < n; j++) { isS[j*i] = true; } } return count; }
优化一下，这个借鉴了CyC2018大神的解法，他在从2开始将每一个素数的倍数索引对应的数组值设置为true的时候，游标变量并不是每次加1，而是每次加上当前素数值，内部循环，游标的初始值是当前素数的平方。
我对此的分析是，大于1的自然数中，既分为质数和合数，也分为奇数和偶数，对于偶数除了2以外一定不是质数，那么通过2就可以将小于n大于2的所有偶数排除掉了，而这些偶数都可以拆分为多个2相加，剩下的就只是奇数了；对于大于2的质数，一定是奇数，但是奇数不一定是质数，所以对于剩下的既是奇数又是合数的数，它是不能被2整除的，能整除它的就只有是奇数，而这些奇数又都可以拆分为奇数个素数相加，所以将游标的递增设置为 每次前进当前素数个步数。
public int countPrimes(int n) { if (n <= 2){ return 0; } int count = 0; boolean[] isS = new boolean[n + 1]; for (int i = 2; i < n; i++) { if (isS[i]){ continue; } count++; for (long j = (long)(i)*i; j < n; j+=i) { isS[(int)j] = true; } } return count; }
在此纪念一下，力扣写了100道了，个中酸甜苦辣都有，继续坚持，为了梦想！！！
原文：https://www.cnblogs.com/yxym2016/p/12961374.html