《算法竞赛进阶指南》0x31质数

本文主要是介绍《算法竞赛进阶指南》0x31质数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义

若一个正整数无法被除了1和它本身之外的任何自然数整除，则称这个数为质数（素数），反之为合数。
对于一个足够大的整数N，不超过N的质数大约有 N/lnN个，分布比较松散。

质数的判定

试除法
若一个正整数N为合数，则存在一个能整除N的数T，其中 $2\leq T \leq \sqrt{N}$ 。

因此，我们只需要扫描 $[2,\sqrt{N}]$ 之间的所有整数，一次检查能否整除N，若不能则N是质数，否则N是合数。

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i <= sqrt(n); i ++ )if (n % 2 == 0) return false;return true;
}

质数的筛选

给定一个整数N，求出[1,n]之间所有的质数，称为质数的筛选问题。

Erathosthenes筛法
Erathosthenes筛法基于这样的思想，任意整数x的倍数都不是质数，我们可以从2开始，从小到大扫描每一个数，把他们的倍数标记为合数。当扫描到一个数时，如果没有被标记，那么就是质数。

void primes(int n)
{memset(st, 0, sizeof st);for (int i = 2; i <= n; i ++ ){if (st[i]) continue;prime[cnt ++ ] = i;for (int j = i; j <= n / i; j ++ ) st[i * j] = 1;}
}

$时间复杂度为 O (n l o g l o g n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ... + 1/ n) = n l o g l o g n$ 。

线性筛法
线性筛法通过“从大到小累积质因子”的方式标记每个合数。
1.依次考虑[2,n]之间的每一个数i。
2.若st[i]=0,说明i是质数，保存下来。
3.扫描每个质数p，令v[i*p]=p.也就是在i的基础上累计一个质因子p。因为p<=i的最小质因子,所以p就是合数i*p的最小质因子。

void primes(int n)
{memset(st, 0, sizeof st);cnt = 0;for (int i = 2; i <= n; i ++ ){if (!st[i]) prime[cnt ++ ] = i;for (int j = 0; i * prime[j] <= n; j ++ ){st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}

每个合数i*p只会被最小质因子p筛一次，时间复杂度为O(n)。

质因数分解

任何一个大于1的正整数都能唯一分解成有限个质数的乘积，可写作：
$N=p_1^{c1}p_2^{c2}...p_m^{cm}$
其中ci为正整数，pi为质数，且 $p_1 < p_2 < ... <pn$ 。

试除法

void divide(int n)
{m = 0;for (int i = 2; i <= sqrt(n); i ++ ){if (n % 2 == 0){p[ ++ m] = i, c[m] = 0;while (n % i == 0) n /= i, c[m] ++ ;}}if (n > 1) p[ ++ m] = 1, c[m] = 1;for (int i = 1; i <= m; i ++ )cout << p[i] << '^' << c[i] << endl;
}

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

例题

acwing196.质数距离

如果直接使用线性筛求出[2,r]之间的所有质数的话时间复杂度为T*10^9，显然会超时，我们考虑使用线性筛求出 $[2,\sqrt{r}]$ 之间所有的素数，对于每个素数，把[l,r]中能被该质数整除的数标记。

时间复杂度分为两部分，线性筛的时间复杂度加上求区间合数的时间复杂度。
前者时间复杂度为 $O(\sqrt{r})$
后者时间复杂度为 $(r-l)/2+(r-l)/3+(r-l)/5+...+(r-l)/\sqrt{r}=O((r-l)*(loglog\sqrt{n}))$
总和为 $O(T*(\sqrt{r}+(r-l)*(loglog\sqrt{n})))$ 。

#include <iostream>
#include <cstring>
using namespace std;
#define N 1000010
typedef long long ll;
bool st[N];
int prime[N];
int cnt = 0;
void init(int n)
{memset(st, 0, sizeof st);cnt = 0;for (int i = 2; i <= n; i ++ ){if (!st[i]) prime[cnt ++ ] = i;for (int j = 0; i * prime[j] <= n; j ++ ){st[i * prime[j]] = true;if (i % prime[j] == 0) break;}}
}
int main()
{int l, r;while (cin >> l >> r){init(500000);memset(st, 0, sizeof st);for (int i = 0; i < cnt; i ++ ){ll p = prime[i];for (ll j = max(2 * p, (l - 1 + p) / p * p); j <= r; j += p)st[j - l] = true;}cnt = 0;for (int i = 0; i <= r - l; i ++ ){if (!st[i] && i + l >= 2) prime[cnt ++ ]  = i + l;}if (cnt < 2) puts("There are no adjacent primes.");else{int minp = 0, maxp = 0;for(int i = 0; i < cnt - 1; i ++ ){int d = prime[i + 1] - prime[i];if (d < prime[minp + 1] - prime[minp]) minp = i;if (d > prime[maxp + 1] - prime[maxp]) maxp = i;}printf("%d,%d are closest, %d,%d are most distant.\n",prime[minp], prime[minp + 1], prime[maxp], prime[maxp + 1]);}}return 0;
}

acwing197.阶乘分解
首先排除先求出阶乘再用试除法分解质因数的方法。
再排除对于1-n每一个整数分解质因数，最后进行整合的方法，因为这样的时间复杂度为 $O(n\sqrt{n})$ ，依然会超时。
考虑枚举质数，因为N！的阶乘的质因数肯定不会大于N，所以找丛2到N的所有质数p。
对于每一个p^k,求其会贡献多少个质数p的数量，即
$\lfloor N/p \rfloor+\lfloor N/p^2 \rfloor+\lfloor N/p^3 \rfloor+...+\lfloor N/p^k \rfloor$
一共有 $log_p^n$ 项，可以以O(1)的时间求出每一项的值。又因为前n个数中质数数量为n/logn，所以 $log_2^n+log_3^n+log_5^n...<log_2^n *n/log_2^n = n$
所以总体时间复杂度为 $O (n)$ 。

#include <iostream>
using namespace std;
#define N 1000010
bool st[N];
int prime[N];
int n, cnt = 0;
typedef long long ll;
void init(int n)
{for (int i = 2; i <= n; i ++ ){if(!st[i]) prime[cnt ++ ] = i;for (int j = 0; prime[j] * i <= n; j ++ ){st[i * prime[j]] =true;if (i % prime[j] == 0)break;}}
}
int main()
{cin >> n;init(n);for (int i = 0; i < cnt; i ++ ){int p = prime[i];int s = 0;for (ll j = p; j <= n; j *= p)s += n / j;printf("%d %d\n", p, s);}return 0;
}