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

定义

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

质数的判定

试除法
若一个正整数N为合数，则存在一个能整除N的数T，其中$2\le T\le \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(nloglogn)=n\ast (1/2+1/3+1/5+1/7+...+1/n)=nloglogn$。

线性筛法
线性筛法通过“从大到小累积质因子”的方式标记每个合数。
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)\ast (loglog\sqrt{n}))$
总和为$O(T\ast (\sqrt{r}+(r-l)\ast (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$
一共有$lo{g}_p^n$项，可以以O(1)的时间求出每一项的值。又因为前n个数中质数数量为n/logn，所以$lo{g}_2^n+lo{g}_3^n+lo{g}_5^n...<lo{g}_2^n\ast n/lo{g}_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;
}