埃氏筛法判断素数

埃氏筛法Sieve of Eratosthenes核心结论埃氏筛法是一种高效求一定范围内素数的算法通过 “标记非素数” 的思路时间复杂度低至 O (n log log n)适用于小到中等范围的素数求解。基于 “素数的倍数一定是非素数” 的数学性质用 boolean 数组 flag 标记数字状态flag[i] true表示 i 是素数flag[i] false表示 i是非素数。例子以 “求小于等于 30 的素数” 为例步骤如下1. 初始化创建长度为 n1 的 boolean 数组 flag索引对应数字 0~n默认先标记 2~n 为素数flag[2..n] true0 和 1 本身不是素数无需标记为 true。2. 筛选过程从第一个素数 2 开始遍历至 √n优化点大于 √n 的合数必有小于 √n 的因子无需后续遍历。○ 若当前数字 i 的 flag [i] 为 true说明 i 是素数则标记其所有倍数为非素数flag[j] false。○ 标记起点从 ii 开始优化点i2、i3…i(i-1) 已被更小的素数标记过无需重复操作每次累加 i 得到下一个倍数。3. 结果收集遍历 flag 数组收集所有 flag [i] true 的索引 i即为小于等于 n 的所有素数。import java.util.ArrayList; import java.util.Scanner; public class SieveOfEratosthenes{ public static void main(String[]args){ Scanner scnew Scanner(System.in); int nsc.nextInt(); ArrayListIntegerprimesnew ArrayListInteger(); //小于2的地方不判断 if(n2){ return; } //定义一个布尔数组来判断是否为素数 boolean[]flagnew boolean[n1]; for(int i2;in;i){ flag[i]true; //初始化全为素数 } for(int i2;i*in;i){ if(flag[i])/*一个数的倍数一定不是素数 如果一个数没有比他小的因数 他就是素数*/{ for(int ji*i;jn;ji){ flag[j]false;//素数的倍数都定为false } } } for (int i2;in;i) { if (flag[i]) { primes.add(i); } } System.out.println(primes); } }#include bits/stdc.h using namespace std; using lllong long; int main() { ll n; cinn; vectorboolx(n1,true);\\定义n1的长度是为了数组下标就代表数0~n x[0]false; x[1]false;\\0 1不用判断直接写一定不能省略 for(ll i2;in;i) { if(x[i]true)//由于循环是从2一个一个加上来的这个数如果还是true { // 那就证明他不是前面所有的数的一个倍数这恰好就是素数的定义 for(int ki*2;kn;ki) { x[k]false;//如果i是素数那i的从2开始的所有倍数都不是素数了 } } } for(ll i2;in;i)//有个小白问学长学长学长为什么不在刚才判断的时候直接 { //输出素数还要再弄一个循环啊 if(x[i]true) //学长如果题目要求找出1000到100000之间的素数直接把这个循环 couti ; //的i的初始值改一下就好了 } return 0; }