素数与筛法

素数的定义

素数定义

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

一个自然数，若且对于所有的，如果能整除(即),那么或。

素数的筛法

1.试除筛

对于一个大于1的数,我们枚举 $到$ 之间的所有整数，如果 $使得$ ,那么为合数（非素数）,否则为素数。复杂度

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.埃氏筛

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

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，所以会在枚举该四个素数的过程中重复枚举到。
欧拉线性筛的关键就在于，使得每个合数只被它的最小质因子筛除，从而保证每个数只会被标记一次。
核心思想：

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

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; // 保证只被最小质因子筛
        }
    }
}

实际上内层循环的次数为：。
用数学公式表示为：
而每个数字只会被其最小质因子标记，实际标记次数远小于,而是接近线性次数。

GCD与LCM

部分公式符号说明

整除符号

如果整数被整数整除,即 $使得$ ,则记作

取余符号

如果 $使得$ ,记作,为对取余后的余数

gcd(求最大公因数)

规定 $对于为、的最大公因数$

lcm(求最小公倍数)

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

辗转相除法的证明

设,则有 $且$

令,其中 $可以得到$ r = a - bq$

由 $可以得到$ ,又

则

因此 $是的公约数$ , $或表示为$

且

设,则有:

由可以得到

因此, $是、$ 的公约数,则

综上可得：且

则,又

则

不断辗转相除

直到 $即$ 时, 这也是最后一层相除

gcd代码

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

lcm(最小公倍数)

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

分别对进行质因数分解,得到:

则有

所以可以得到

互质

如果两个数只有1这一个公因数，那么这两个数互质，即,则互质

快速幂

快速幂的原理

如果我们要求解,可以有以下考虑：

$即为偶数$ ,向下递归求解,然后将得到的结果平方,即
$即是奇数$ ,向下递归求解,然后将结果平方后乘以b,即

每次求解的大小会减半，直到递归到,所以时间复杂度为

快速幂的实现

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;}

基础数论入门

目录

本文目录