素数

定义：

素数又称质数，是指一个大于$1$的正整数，如果除了$1$和它本身之外，没有其他的约数，反之就是合数，$1$既不是素数也不是 合数；

素数的判定：

1.穷举法 $O(√(n))$：

1.枚举$2$~$√(n)$的整数；

2.如果在$2$~$sqrt(n)$中，有大于$1$个约数，就是合数，反之为素数；

2.筛法-埃氏筛：

1.初始化序列：

1.列出从$2$到目标数$n$的所有整数，默认标记为素数（未被筛除）；

2.筛选过程：

1.从最小的素数$2$开始，将其所有倍数（$4, 6, 8,...$）标记为合数；

2.继续处理下一个未被标记的数（如$3$），同样筛除其所有倍数（$9, 12, 15,...$）；

3.重复上述步骤，直到处理到$√n$为止（因为任何大于√n的合数必有一个小于$√n$的因数）；

3.终止条件：

1.当所有小于等于$√n$的素数均完成倍数筛除后，剩余未被标记的数即为素数；

3.筛法-线筛：

1.初始化：

1.创建布尔数组$isPrime[]$，初始标记所有数为素数（$true$）；

2.维护一个质数列表$primes[]$，用于存储已发现的素数；

2.遍历筛选：

1.从$2$开始遍历到目标数$n$：

1.若当前数$i$未被标记为合数（$isPrime[i] = true$），则将其加入$primes[]$。

2.遍历$primes[]$中的质数$p$，筛除合数$i * p$：

1.若$i$ % $p == 0$，说明$p$是$i$的最小质因数，此时$i * p$的最小质因数也是$p$，筛除后终止内层循环（避免重复标记）；

2.否则，$p$是$i * p$的最小质因数，直接筛除；

3.终止条件：

1.当$i * p > n$时停止内层循环，防止越界；

原文：

# 素数

## 定义：

素数又称质数，是指一个大于$1$的正整数，如果除了$1$和它本身之外，没有其他的约数，反之就是合数，$1$既不是素数也不是
合数；

## 素数的判定：

### 1.穷举法 $O(√(n))$：

1.枚举$2$~$√(n)$的整数；

2.如果在$2$~$sqrt(n)$中，有大于$1$个约数，就是合数，反之为素数；

### 2.筛法-埃氏筛：

#### 1.初始化序列：

1.列出从$2$到目标数$n$的所有整数，默认标记为素数（未被筛除）；

#### 2.筛选过程：

1.从最小的素数$2$开始，将其所有倍数（$4, 6, 8,...$）标记为合数；

2.继续处理下一个未被标记的数（如$3$），同样筛除其所有倍数（$9, 12, 15,...$）；

3.重复上述步骤，直到处理到$√n$为止（因为任何大于√n的合数必有一个小于$√n$的因数）；

#### 3.终止条件：

1.当所有小于等于$√n$的素数均完成倍数筛除后，剩余未被标记的数即为素数；

### 3.筛法-线筛：

### 1.初始化：

1.创建布尔数组$isPrime[]$，初始标记所有数为素数（$true$）；

2.维护一个质数列表$primes[]$，用于存储已发现的素数；

#### 2.遍历筛选：

1.从$2$开始遍历到目标数$n$：

1.若当前数$i$未被标记为合数（$isPrime[i] = true$），则将其加入$primes[]$。

2.遍历$primes[]$中的质数$p$，筛除合数$i * p$：

1.若$i$ % $p == 0$，说明$p$是$i$的最小质因数，此时$i * p$的最小质因数也是$p$，筛除后终止内层循环（避免重复标记）；

2.否则，$p$是$i * p$的最小质因数，直接筛除；

#### 3.终止条件：

1.当$i * p > n$时停止内层循环，防止越界；