当前位置：首页 > news >正文

NOI大纲——普及组——素数筛法

news 来源：原创 2024/9/20 9:08:57

素数筛的进化史

1.最为基础的筛法——试除法

时间复杂度 $O(n^2)$

int a[10000],tot=0,n;
for (int i=2;i<=n;i++){bool flag=false;for (int j=2;j<i;j++){if (i%j==0)flag=true;}if (flag==false){a[tot]=i;tot++;}
}
for (int i=0;i<tot;i++){cout<<a[i]<<" ";
}
//筛1到n的质数

2.试除法的优化

时间复杂度 $O(n\times \sqrt{n})$

int a[10000],tot=0,n;
for (int i=2;i<=n;i++){bool flag=false;for (int j=2;j<=sqrt(i);j++){if (i%j==0)flag=true;}if (flag==false){a[tot]=i;tot++;}
}
for (int i=0;i<tot;i++){cout<<a[i]<<" ";
}
//筛1到n的质数

埃拉托色尼筛法（Eratosthenes Sieve）

埃拉托色尼筛法是一种古老且高效的算法，用于找出某个范围内所有的素数。它的工作原理基于反复标记出合数（即非素数）。其核心思想如下：

设定一个范围，例如从2到某个整数n。
从最小的素数2开始，标记2的所有倍数为合数（非素数）。
找到下一个未被标记的数，它是下一个素数，然后标记这个素数的所有倍数。
重复步骤3，直到到达范围的尽头。

下面是埃拉托色尼筛法的详细步骤及代码实现：

步骤详解

初始化数组：创建一个布尔数组isPrime，其大小为n+1，所有元素初始化为true。这个数组用于标记是否为素数。
标记合数：从2开始，对于每一个isPrime为true的数i，标记i的所有倍数为false。
终止条件：i的值不超过 $\sqrt{n}$ 。因为如果i的值超过 $\sqrt{n}$ ，i的倍数中最小的一个已经大于n，因此没有必要继续标记。

代码实现

int a[100000], tot = 0; // 存储素数的数组和计数器
bool ais[100000]; // 标记数组for (int i = 2; i <= n; i++) { // 从2开始遍历到nif (ais[i] == 0) { // 如果i没有被标记为合数a[tot++] = i; // 将i存入素数数组for (int j = 2; j < n && j * i <= n; j++) { // 从2开始标记i的倍数ais[i * j] = 1; // 标记i的倍数为合数}}
}for (int i = 0; i < tot; i++) { // 输出所有素数cout << a[i] << " ";
}

示例

假设我们要找出30以内的所有素数：

初始化：isPrime数组为[true, true, true, …, true]，长度为31。
从2开始，标记2的倍数：4, 6, 8, 10, …, 30都标记为false。
下一个未标记的数是3，标记3的倍数：6, 9, 12, 15, …, 30都标记为false。
下一个未标记的数是5，标记5的倍数：10, 15, 20, 25, 30都标记为false。
继续下去，直到√30≈5.48。

结果：2, 3, 5, 7, 11, 13, 17, 19, 23, 29为素数。

欧拉筛（Euler’s Sieve）

欧拉筛法是埃拉托色尼筛法的一种改进版本，它在标记合数时避免了重复工作，因此效率更高。欧拉筛法利用了以下性质：

每个合数都可以表示为若干素数的乘积。
对于每个素数p，标记其倍数时，只需从它开始标记，不需要重复标记已经被其他素数标记过的数。

步骤详解

初始化数组：与埃拉托色尼筛法类似，初始化一个布尔数组isPrime和一个存储素数的数组a。
标记合数：对于每一个数i，如果它是素数，将其存入数组a，然后标记其所有的合数。
终止条件：当i的值达到n时停止。

代码实现

const int MAXN = 100000; // 定义常量，最大范围
int a[MAXN], tot = 0; // 存储素数的数组和计数器
bool isPrime[MAXN]; // 标记数组void eulerSieve(int n) {fill(isPrime, isPrime + n + 1, true); // 初始化标记数组，所有元素设为trueisPrime[0] = isPrime[1] = false; // 0和1不是素数for (int i = 2; i <= n; i++) { // 从2开始遍历到nif (isPrime[i]) { // 如果i是素数a[tot++] = i; // 将i存入素数数组}for (int j = 0; j < tot && a[j] * i <= n; j++) { // 遍历所有已存入的素数isPrime[a[j] * i] = false; // 标记a[j]和i的乘积为合数if (i % a[j] == 0) break; // 如果i是a[j]的倍数，停止标记}}// 输出所有素数for (int i = 0; i < tot; i++) {cout << a[i] << " ";}cout << endl;
}