西北工业大学NOJ平台：质数与分解质因数专题（共4篇题解）

发表于 2024-10-17 更新于 2024-10-19

前言

质数和分解质因数是非常基本的数学知识，在各类算法中都有非常广泛的运用，本篇文章将大致介绍在这方面常用的一些算法，并以NOJ中的题目作为示例：

Eratosthenes筛法
质因数分解
Euler筛法
Euler函数

前置知识

质数

设一个正整数p不为0或1。如果p除了平凡约数（即其自身和1）外没有其他约数，那么称p为质数（或称素数/不可约数）。

互质

互质是公约数只有1的两个整数，叫做互质整数。

最大公约数

指两个或多个整数共有约数中最大的一个，通常记作(a, b)或gcd(a, b)。

通常，我们运用辗转相除法来求两个数的最大公约数，以下是代码实现：

1
2
3

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

正确性证明：若b不为0，则a可以被表达为a = kb + r的形式，其中k为整数，k = [a / b]（[]表示高斯函数），r = a % b（%表取余操作）。当某个因数c满足b % c == 0且a % c == 0，则其必然满足r % c == 0，所以a与b的最大公因数必然是b与r的最大公因数；
若b为0，则最大公因数为a。
所以，上方递推公式成立。

(31-40)素数

题面

题面（素数）

解法：Eratosthenes筛法

Eratosthenes筛法，又名埃氏筛，是一种获取[1, n]之内所有质数的算法，它通过遍历，将指定一个数的所有倍数从集合中排除，来筛选没有平凡约数的数作为质数，以下给出埃氏筛的C++实现代码。

vector<int> primes, vis;
void get_primes(int n) {
    vis.resize(n + 1, 0);
    for(int i = 2; i <= n; i++) {
        if(vis[i] == 0) {
            primes.push_back(i);
            for(int j = i; j <= n; j += i) vis[j] = 1;
        }
    }
}

正确性说明：任何一个合数n总存在介于(1, n)内的至少一个因数，当循环执行到i = n之前，必然会有i = j (j < n)的循环情况将其排除出质数列表。

以此为基础，给出本题题解如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Eratosthenes 筛法
    vector<int> vis;
    int min, max;
    int result = 0;
    cin >> min >> max;
    vis.resize(max + 1, 0);
    for (int i = 2; i <= max; i++) {
        if (vis[i] == 0) {
            if (i >= min) { result++; }
            for(int j = i; j <= max; j += i) vis[j] = 1;
        }
    }
    cout << result;
}

扩展

所有大于3的素数都可以表示为6n + 1或6n - 1的形式，所以所有可以被表示为6n + 2 6n + 3 6n + 4 6n形式的整数一定不是素数，可以用该方案快速判定一个数是否为质数，不过该算法对于优化埃氏筛没有太大帮助。

(21-30)阶乘倍数

题面

题面（阶乘倍数）

解法：分解因数

如果应用暴力方案的话，那么暂存的阶乘结果会很快越界，所以我们采取其他的方案。在这里我们做分解因数的方法。

我们从i = 2开始递增循环，对于目标数target，每一次循环都计算gcd(i, target)，并将target除去gcd(i, target)。不断循环直到target被除尽（即target == 1），此时的target经过了2, 3, 4 ... i的所有因数的相约，所以target现在就是i!的约数之一，满足i! % target == 0。

以下是示例代码：

#include <iostream>
using namespace std;

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

bool isPrime(long long target) {
    for (long long i = 2; i * i <= target; i++) {
        if (!(target % i)) { return false; }
    }
    return true;
}

long long getMaxNotRepeatedFactors(long long target) {
    if (target == 1 || isPrime(target)) { return target; }
    // 如果target是质数则直接返回它
	for (long long i = 2; ; i++) {
        long long greatestCommonDiv = gcd(i, target);
        if (greatestCommonDiv != 1) {
            target /= greatestCommonDiv;
        }
        // 将原数拆解为多个因数
        if (target == 1) { return i; }
    }
    return -1;
}

int main() {
    long long target; cin >> target;
    long long result = getMaxNotRepeatedFactors(target);
    cout << result;
    return 0;
}

(41-50)素数筛选法

题面

题面（素数筛选法） ;

解法：Euler筛法

Euler筛法是Eratosthenes筛法的升级版，在Eratosthenes筛法中，一个拥有多个约数的合数实际上被筛选了多遍，如果我们可以让一个合数只被其最小的那个约数筛选一遍的话，我们就能提高筛选的效率，这样的话，我们引入Euler筛法：

bool[] eulerGetPrimes(int target) {
    bool isPrimeList[target + 1]; // 质数信息，被标记为1时不是质数
    vector<int> primes; // 质数表
    for (int i = 2; i <= target; i++) {
        if (!isPrimeList[i]) primes.push_back(i);
        for (int p : primes) {
            if (p * i > target) break;
            isPrimeList[p * i] = 1; // 该数的倍数一定不是质数
            if (i % p == 0) break; // 之后不用筛了，因为那样的话不是使用其最小质因数
        }
    }
    return isPrimeList;
}

Euler筛法中，若当前用来筛选的约数i可以整除已知质数表中用作倍数的p，则此时i乘上质数表中其它的质数也一定是p的倍数，会被p筛去，所以无需继续筛除，执行break;退出。

由此给出本题题解：

#include <iostream>
#include <vector>
using namespace std;

// 定义eulerGetPrimesCnt(int target)，和上方代码一致。

int main() {
    int target; cin >> target;
    int result = eulerGetPrimesCnt(target);
    cout << result;
    return 0;
}

(31-40)运动会

题面

题面（运动会）

解法：Euler函数

容易想到，去除队长本人(0, 0)不可见，(1, 0)可见和(0, 1)可见以外，对于任意其它队员(x, y)，其能被看见的充要条件是x与y互质（这样就不存在(x / a, y / a)（a为大于1的正整数）的队员挡住他）。

所以，我们实际上就是要找出(x, y)中x y互质的人有几个，这里使用gcd(int a, int b)一个一个遍历的话会超时，我们为了过题，在此引入Euler函数，它的功能是计算[1,x]中与x互质的数的数量。

Euler函数的C++实现如下：

int eulerPhi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            // 相当于ans -= ans / i;
            // 小于ans的数中是i的倍数者全部被去除
            while (n % i == 0) n /= i;
            // 这个因数已经被去除过了，因此把它从n中除去
        }
    }
    if (n > 1) { ans = ans / n * (n - 1); }
    // 没被除尽后的处理
    return ans;
}

Euler函数的运行原理如下：

设置答案ans为n，代表[1, n]区间内有n个数。
现在我们把不互质的数从中去除，开始从i = 2循环，如果i ^ 2 <= n而且n % i == 0，那么执行ans -= ans / i;，这一步骤主要是为了将n的约数之一的i的所有倍数从[1, n]中划去，这样的数一共有ans / i个。
在去除了这些数之后，由于i作为约数已经执行了删除，所以我不希望过会执行到2i或者其它时i的整数倍作为约数时再删除一遍，所以我执行while (n % i == 0) n /= i;，将i及其整数倍的约数从n中除去，这样n % i == 0的限制条件就会避免这些情况。
如此循环直到跳出，如果n不为1，说明其还存在未除去的约数（这是由于剩下的n本身就是个质数），再做一轮去除。
返回ans，计算完成。

基于此，我们给出本题题解：

#include <iostream>
using namespace std;

// 引入欧拉函数，计算[1,x]中与x互质的数的数量
// 此处算法详解见OI Wiki：https://oi-wiki.org/math/number-theory/euler-totient/
int eulerPhi(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) { ans = ans / n * (n - 1); }
    return ans;
}

int main() {
    // 我们假设队长是在左上角的，这样方便计算
    int squadSize; cin >> squadSize;
    if (squadSize == 1) { cout << 0; return 0; }
    // 如果(x,y)中，x与y互质，则这个人可见；特殊地，x与y其中一个为0，一个为1的人也可见
    int result = 0;
    for (int i = 1; i < squadSize; i++) {
        result += eulerPhi(i);
    }
    result = result * 2 + 1;
    // 遍历方阵，找到这样的人有几个
    cout << result;
    return 0;
}

后记

本篇文章知识点：

Eratosthenes筛法
质因数分解
Euler筛法
Euler函数