埃拉托斯特尼算法（埃氏筛）【简单】

核心思想筛除合数留下素数若x是素数那么x的倍数一定不是素数那么这些数就可以直接排除不必后续再次逐一遍历来降低效率。既然要记录x的倍数都不为素数显然我们在进行筛除之前就要创建一个容器来保存所有数指要求范围的所有数是否为素数的状态。那么我们就通过一个数组isPrime[]来实现如果数i为素数那么isPrime[i]则为1否则为0然后我们便从小到大遍历若数为素数则将其倍数不包括该素数本身都标记为合数即数组对应下标值设为0如此一来我们遍历完后只要看数组值为1的就是素数那么记录素数数量甚至输出所有素数等操作都将变得游刃有余了。正确性说明首先我们通过上述的基本思想我们可知这个算法就是把里面的合数挑出来标记为0,那么其实在数组创建时我们就是先全都标记为1的即先全认为是素数然后通过算法所筛出的确定的素数再来跳出合数标记为0故全程数组的数就是一直在从1变为0也就是开始说的从中挑出合数。那么这个方法就显然不会将质数标记成合数即从这个方法的感觉中就可确定质数不会轻易标记成合数但合数可能不会被发现从而被当作素数而我们刚拿到这个方法时难免会感到一种不确定感为什么我一定能够确定遍历到某个素数即数组值为1时它一定就是素数呢会不会它本是合数只是之前的遍历操作中未将它发现从而有了漏网之鱼呢我们现在来一探究竟首先这个方法一定不会将素数标记为合数。当我们从小到大遍历时若数x是合数那么根据合数的性质知x至少有一个素数因数注意1不为素数我们就记为y那么从小到大遍历中我们会在x之前先遍历到y那么在把y的倍数标记为合数的时候定然就会把x标记为了合数因此不会出现漏网之鱼的合数未被标记导致误成为素数的情况。优化当我们知道了它的正确性的成立原因道理接下来的优化操作就容易理解了对于质数x若按先前的方式从2x开始标记为合数其实是会有重复操作的会不会这个2x在之前就已经被标记为了合数的呢如果是那我这次的操作岂不是白干了那我们现在就得研究从什么时候开始标记既不会遗漏也不会重叠其实从上一节中的合数 x 至少有一个素数因数 y我们其实就能猜到在x*x之前数都不需要标记因为之前的数k*x 其中 k 取值从 2 ~ x-1中的k是小于x的那么有两种情况一是k为质数那么在遍历到k时k*x一定会被标记为合数的二是k不为质数那么也是照前面说的一样k必有一个素数因数y那k*x也必会有一个素数因数y那显然在遍历到y时k*x一定就会被标记为合数的。而x*x又是只有因数x和1所以其只能靠x来标记为合数故从x*x开始标记既保证了之前的已经被标记也保证了开始的x*x只能靠x标记因此从x*x开始就是最优“起点”。算法步骤初始化筛子创建长度为n 1的bool类型int也未尝不可数组isPrime[n 1]其中数组的索引就代表对应的数字而数组的值则表明其对应数字是否为素数比如isPrime[11] 1就代表数字11为素数然后数组初始时全为true但注意要把下标0、1位置设置为false这两个数规定了不为素数筛除合数从i 2遍历到 $\sqrt{n}$ 若isPrime[i] true则把i的所有倍数记为false。当然优化后就是从i*i开始标记为false。结果提取遍历结束后值为true的索引即是1 ~ n之间的所有素数。示例代码 Cclass Solution { public: int Primes(int n) { if (n 2) return 0; if (n 3) return 1; vectorbool IsPrime(n, true); for(int i 3; i * i n; i 2){ if(IsPrime[i]){ for(int j i * i; j n; j i){ IsPrime[j] false; } } } // 此时容器内的所有数都筛选完了接下来就可按照题意进行想要的操作 // 如果为了进一步高效甚至可以在进行筛选的过程中同步进行一些操作但一定要保证在操作时所操作的数字已经筛选过了 };