素数与筛法

素数的定义

素数定义

素数（$prime\ number$）是一个大于1的自然数,如果它仅有两个正整数因子:1和它自身。换句话说，素数是只能被1和它自己整除的数。
形式上，可以表示为？

一个自然数$p$,若$p > 1$且对于所有的$d ∈ N$,如果$d$能整除$p$(即$p\ mod\ d = 0$),那么$d = 1$或$d = p$。

素数的筛法

1.试除筛

对于一个大于1的数$n$,我们枚举$1到n-1$之间的所有整数$i$,如果$∃i,使得n\ mod\ i = 0$,那么$n$为合数（非素数）,否则$n$为素数。复杂度$O(\sqrt{n})$

bool isPrime(int n) {
    if(n <= 1) return false;
    for(int i = 2; i * i <= n; i++)
        if(n % i == 0) return false;
    return true;
}
......

2.埃氏筛

标记素数在范围内的所有倍数为非素数，因为对于一个合数的倍数，肯定也是一个比它小的素数的倍数。因为合数肯定有素数因子，即合数至少是一个素数的倍数。
所以合数的倍数也是素数的倍数，在枚举过程中，我们遇到一个合数选择跳过，遇到素数，那么标记该素数的所有倍数为非素数。复杂度$O(n\log \log n)$

bool is_prime[MAXN];
void get_prime(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i*i <= n; i++)
        if(is_prime[i])
            for(int j = i*i; j <= n; j += i)
                is_prime[j] = false;
}

3.欧拉筛

我们发现埃氏筛中，有的数会被重复枚举到。即一个数可以是多个素数的倍数。
比如210,它的质因子同时包含了2、3、5、7,所以会在枚举该四个素数的过程中重复枚举到。
欧拉线性筛的关键就在于，使得每个合数只被它的最小质因子筛除，从而保证每个数只会被标记一次。
核心思想？

对于每个数$i$,枚举所有小于等于$i$的最小质因数$p$,标记$i*p$为合数。
当$i$能被$p$整除时，说明$p$是$i$的最小质因子，此时停止标记。

vector<int> primes;        // 存储质数
bool is_composite[MAXN];   // 标记是否为合数

void get_prime(int n) {
    for(int i = 2; i <= n; i++) {
        if(!is_composite[i]) {
            primes.push_back(i); // i 是质数
        }
        for(int p : primes) {
            if (i * p > n) break; // 超过范围,退出
            is_composite[i * p] = true; // 标记 i*p 为合数
            if (i % p == 0) break; // 保证只被最小质因子筛
        }
    }
}

实际上内层循环的次数为：$\frac{n}{i}$。
用数学公式表示为：$\sum_{i=2}^{n}\ \frac{n}{i}≈n\sum_{i=2}^{n}\ \frac{1}{i}≈n\ln n$
而每个数字只会被其最小质因子标记，实际标记次数远小于$n\ln n$,而是接近线性次数$n$。

GCD与LCM

部分公式符号说明

整除符号 $\mid$

如果整数$a$被整数$p$整除，即$\exists k \in Z,使得a = kp$,则记作$p\mid a$

取余符号 $mod$

如果$\exists m \in Z,使得a=kp+m$,记作$a\ mod\ p = m$,$m$为$a$对$p$取余后的余数

gcd(求最大公因数)

规定$对于a,b \in Z,gcd(a,b)为a、b的最大公因数$

lcm(求最小公倍数)

辗转相除法求gcd(最大公因数)

辗转相除法的证明

设$d=gcd(a,b)$,则有$d\mid a且d\mid b$

令$a=bq+r$,其中$0\le r < b$ 可以得到：$r = a - bq$

由$d\mid b可以得到d\mid bq$,又$d\mid a$

则$d\mid r$

因此$d是b,r的公约数$,$r = a - bq\ 或表示为r = a\ mod\ b$

且$d ≤ gcd(b,r)$

设$d’ = gcd(b,r)$,则有：$d’\mid b,d’ \mid r$

由$a = bq + r$可以得到$d’\mid a$

因此：$d’是a、b$的公约数，则$d’ ≤ gcd(a,b)$

综上可得：$d’ = gcd(b,r) ≤ gcd(a,b)$且$d = gcd(a,b) ≤ gcd(b,r)$

则$gcd(a,b) = gcd(b,r)$,又$r = a\ mod\ b$

则$gcd(a,b) = gcd(b,a\ mod\ b)$

不断辗转相除

直到$r = 0,即a = bp$时：$gcd(a,b) = b$ 这也是最后一层相除

gcd代码

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

lcm(最小公倍数)

根据算数基本定理,任何大于1的整数都可以唯一的分解成为一组质数的乘积，而且这种分解是唯一的。

分别对$a,b$进行质因数分解，得到？

$a = {p_1}^{\alpha _1} \times {p_2}^{\alpha _2} \times {p_3}^{\alpha _3} \times ··· \times {p_n}^{\alpha _n}$

$b = {p_1}^{\beta _1} \times {p_2}^{\beta _2} \times {p_3}^{\beta _3} \times ··· \times {p_n}^{\beta _n}$

则有

$gcd(a,b) = {p_1}^{min(\alpha _1,\beta _1)} \times {p_2}^{min(\alpha _2,\beta _2)} \times {p_3}^{min(\alpha _3,\beta _3)} \times ··· \times {p_n}^{min(\alpha _n,\beta _n)}$

$lcm(a,b) = {p_1}^{max(\alpha _1,\beta _1)} \times {p_2}^{max(\alpha _2,\beta _2)} \times {p_3}^{max(\alpha _3,\beta _3)} \times ··· \times {p_n}^{max(\alpha _n,\beta _n)}$

$a\times b = {p_1}^{\alpha _1+\beta _1} \times {p_2}^{\alpha _2+\beta _2} \times {p_3}^{\alpha _3+\beta _3} \times ··· \times {p_n}^{\alpha _n+\beta _n}$

所以可以得到$\frac{a\times b}{gcd(a,b)} = lcm(a,b)$

互质

如果两个数只有1这一个公因数，那么这两个数互质，即$gcd(a,b) = 1$,则$a,b$互质

快速幂

快速幂的原理

如果我们要求解$b^p$,可以有以下考虑？

$p = 0,b^0=1$
$p = 2n,即p为偶数$,向下递归求解$b^n$,然后将得到的结果平方，即$b^{2n} = b^n\times b^n$
$p = 2n+1,即p是奇数$,向下递归求解$b^n$,然后将结果平方后乘以b,即$b^{2n+1} = b\times b^n \times b^n$

每次求解$p$的大小会减半，直到递归到$p = 0$,所以时间复杂度为$O(\log_2 p)$

快速幂的实现

long long qpow(int y,int x)
{
	if(x == 0) return 1;
	long long s = qpow(y,x / 2);
	if(x % 2 == 0) return s * s % mod;
	else return s * s % mod * y % mod;
}

当然调用递归函数会导致常数较大，你可以选择非递归的写法，下面提供一下？

long long qpow(long long y,long long x)
{
	if(x == 0) return 1;
	long long s = 1;
	while(x)
	{
		if(x&1) s = s * y % mod; // 为奇数
		y = y * y % mod;
		x >>= 1;
	}
	return s;
}

当然你也可以用一行代码来实现

1	int qpow(int a, int b) {int res = 1; for(; b; b >>= 1, a = a * a % MOD) if (b & 1) res = res * a % MOD; return res;}

基础数论入门

目录

本文目录