质数

定义 : 在大于1的整数(2, 3, 4, …)中，如果只包含1和本身这两个约数，就被称为质数，或者称为素数。

合数的定义与质数相对:
定义 : 在大于1的整数中， 除了能被1和本身整除外，还能被其他数（0除外）整除的数。

最小的质数是2，最小的合数是4。

试除法–质数判定、分解质因数

用试除法， 可以$O(\sqrt{n})$判断某一个数是否是质数，或者对某一个数分解质因数

不难发现，一个数是不是质数其实就是看有没有约数，而约数总是成对出现的，具体来说：

如果${n}$存在约数${d}$，那么也必存在约数${\frac{n}{d}}$，
因此只需要令$d <= \frac{n}{d}$，枚举这对约数中较小的那个，就能把时间复杂度从${O(n)}$优化到${O(\sqrt{n})}$。

// 判断n是否是质数
bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
            return false;
    return true;
}

// 对n分解质因数
void divide(int n) {
    for (int i = 2; i <= n / i; i ++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt ++;
            }
            printf("%d %d\n", i, cnt);
        }
    }
    
    // 特判： 根号n的那个因子
    if (n > 1) printf("%d %d\n", n , 1);
    puts("");
}

质数筛–返回从1到n的质数数组

朴素筛

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

埃氏筛

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

线性筛

用埃氏筛，O(n)判断(1 ~ n)中所有的质数，合数在st[]中为true，质数在prime[]中存储

int prime[N];
bool st[N];
int cnt = 0;

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

最大公约数

最大公约数即为 Greatest Common Divisor，常缩写为 gcd.

int d = gcd(int a, int b);

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

最小公倍数

最小公倍数即为Least Common Multiple，常缩写为 lcm.

最小公倍数 = 两数之积 / 最大公约数，所以只需要记得最大公约数的求法即可。

int m = lcm(int a, int b);

int lcm(int a, int b) {
  return a * b / (gcd(a, b));
}

C++14 : __gcd(a, b) (Defined in header <algorithm>)

C++17：gcd(a, b) 和 lcm(a, b) (Defined in header <numeric>)