企业官网建设流程全解析

埃氏筛法（Sieve of Eratosthenes）

核心结论：埃氏筛法是一种高效求一定范围内素数的算法，通过 “标记非素数” 的思路，时间复杂度低至 O (n log log n)，适用于小到中等范围的素数求解。基于 “素数的倍数一定是非素数” 的数学性质，用 boolean 数组 flag 标记数字状态，flag[i] = true表示 i 是素数，flag[i] = false表示 i是非素数。

例子：

以 “求小于等于 30 的素数” 为例，步骤如下：

1. 初始化：创建长度为 n+1 的 boolean 数组 flag（索引对应数字 0~n），默认先标记 2~n 为素数（flag[2..n] = true），0 和 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 sc=new Scanner(System.in); int n=sc.nextInt(); ArrayList<Integer>primes=new ArrayList<Integer>(); //小于2的地方不判断 if(n<2){ return; } //定义一个布尔数组来判断是否为素数 boolean[]flag=new boolean[n+1]; for(int i=2;i<=n;i++){ flag[i]=true; //初始化全为素数 } for(int i=2;i*i<=n;i++){ if(flag[i])/*一个数的倍数一定不是素数 如果一个数没有比他小的因数 他就是素数*/{ for(int j=i*i;j<=n;j+=i){ flag[j]=false;//素数的倍数都定为false } } } for (int i=2;i<=n;i++) { if (flag[i]) { primes.add(i); } } System.out.println(primes); } }

#include <bits/stdc++.h> using namespace std; using ll=long long; int main() { ll n; cin>>n; vector<bool>x(n+1,true);\\定义n+1的长度是为了数组下标就代表数0~n x[0]=false; x[1]=false;\\0 1不用判断，直接写（一定不能省略） for(ll i=2;i<=n;i++) { if(x[i]==true)//由于循环是从2一个一个加上来的，这个数如果还是true， { // 那就证明他不是前面所有的数的一个倍数，这恰好就是素数的定义 for(int k=i*2;k<=n;k+=i) { x[k]=false;//如果i是素数，那i的从2开始的所有倍数都不是素数了 } } } for(ll i=2;i<=n;i++)//有个小白问学长：学长学长，为什么不在刚才判断的时候直接 { //输出素数，还要再弄一个循环啊 if(x[i]==true) //学长：如果题目要求找出1000到100000之间的素数，直接把这个循环 cout<<i<<' '; //的i的初始值改一下就好了 } return 0; }