数论入门 - 质因数分解

一、课程目标

1. 唯一分解定理
2. 朴素算法
3. 算法优化

二、目标详解

1、唯一分解定理

唯一分解定理（又称算术基本定理） ，即：每个大于$1$的自然数，要么本身就是质数，要么可以写为$2$个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

对任意大于 $1$ 的正整数 $n$，设 $n$ 的质因子分别为 $p_1,p_2,\dots p_k$，则 $n$ 一定能分解为上述质因子若干次幂的乘积，即 ${\displaystyle n=p_1^{c_1}{p}_2^{c_2}\dots p_k^{c_k}}$。并且这种分解方式是唯一的，也就是不存在另一种分解方式使得对应质因子的指数不同。

每个合数都可以写成若干质数因子相乘的形式，这种形式叫做质因子分解。

例如：$60=2\times 2\times 3\times 5$ (指数形式：$60=2^2\times 3^1\times 5^1$)。

例如：$6936=2^3\times 3\times {17}^2,1200=2^4\times 3\times 5^2,5207=41\times 127$ 。

分解质因数只针对合数，因为质数没有其它质因子。

2、质因数分解

朴素算法

假设 ${\displaystyle n=p_1^{c_1}{p}_2^{c_2}\dots p_k^{c_k}}$ 的质因子分解形式，其中 $p_1...p_k$ 为从小到大的质因子。

那么我们可以循环从 $n$ 中剥出所有的 $p_i$，以分解所有的质因子 $2$ 为例：

while(n % 2 == 0) {
    cout << 2 << " ";
    n /= 2;
}

质因子从小到大被剥离，最后 $n$ 就变成了 $1$，此时就循环完成了。

例如：$100=2\times 2\times 5\times 5$，剥出 2 2 5 5 后，$n$ 就剩下 $1$.

算法代码如下：

for(int i=2; n>1; i++)
    while(n%i==0) {
        cout<<i<<" ";
        n /= i;
    }

时间复杂度：如果 $n$ 是一个很大的质数例如 $1e9+7$，$i$的枚举范围从$2$到$n$，时间复杂度为 $O(n)$，会超时。

算法优化

朴素算法超时，原因是枚举的范围太大了，那这个范围是否可以缩小呢？

回顾 唯一分解定理 ：对任意大于 $1$ 的正整数 $n$，设 $n$ 的质因子分别为 $p_1,p_2,\dots p_k$，则 $n$ 一定能分解为上述质因子若干次幂的乘积，即 ${\displaystyle n=p_1^{c_1}{p}_2^{c_2}\dots p_k^{c_k}}$。并且这种分解方式是唯一的，也就是不存在另一种分解方式使得对应质因子的指数不同。

引理：对任意大于 $1$ 的正整数 $n$， $n$ 至多有一个大于 $\sqrt{n}$ 的质因子。假设该质因子存在，它在唯一分解式中的指数一定是 $1$。

证明：

1. 假设 $n$ 有两个大于 $\sqrt{n}$ 的质因子 $p,q$，写出 $n$ 的唯一分解式 $n=tpq>t\sqrt{n}\sqrt{n}=tn$，其中 $t\ge 1$。得 $n>tn$，矛盾。这就证明了至多只有一个大于 $\sqrt{n}$ 的质因子。
2. 在上式中取 $p=q$，矛盾仍成立。这就证明了若唯一大于 $\sqrt{n}$ 的质因子存在，则它在唯一分解式中的指数一定是 $1$。

质因子分解：根据上述引理，只需要枚举 $i=2\sim \sqrt{n}$，通过试除可以求出 所有小于 $\sqrt{n}$ 的质因子。在 $n$ 除掉这些质因子后如果不为 $1$，则剩下的数就是那个大于 $\sqrt{n}$ 的质因子。对于一次查询，时间复杂度 $O(\sqrt{n})$。

以上判断，其实与查找一个数$n$的所有因数使用到的sqrt(n) 思路一致！

int n;
cin >> n;
for (int i = 2; 1ll * i * i <= n; i++) { //i*i如果超过int，就需要转为long long，1ll就是long long 类型的1
    while (n % i == 0) {
        cout << i << " ";
        n /= i;
    }
}
if (n != 1) {  // 如果n本身是质数
    cout << n << " ";
}

演示-质因子分解

题目描述

输入一个整数n，求其质因数。

输入样例

100

输出样例1

2 2 5 5

练习-序列质因子分解

题目描述

输入 $n$ 个数，输出每个数的质因子。

输入格式

• 第一行 $n$
• 第二行 $n$ 个数

输出格式

• $n$ 行，每行都是对应的质因子

输入样例

3
12 50 240

输出样例

2 2 3 
2 5 5 
2 2 2 2 3 5

数据范围

• $40\mathrm{\%}：n<=100,a_i<={10}^5$
• $100\mathrm{\%}：n<={10}^5,a_i<={10}^6$

code:

#include <iostream>
using namespace std;
long long n,x;
int main() {
  cin >> n;
  while(n--) {
    cin >> x;
    for (int i = 2; 1ll * i * i <= x; i++) {
      while (x % i == 0) {
        cout << i << " ";
        x /= i;
      }
    }
    if (x != 1) {  // 如果n本身是质数
      cout << x << " ";
    }
    cout << endl;
  }
  return 0;
}

练习-质因子序列

题目描述

对于 $n$ 个正整数 $a_i$ 组成的序列，输出构成所有 $a_i$ 的最小公倍数的质因子序列，从小到大排列。

输入格式

• 第一行 $n$
• 第二个 $n$ 个正整数

输出格式

• 最小公倍数的质因子序列，从小到大排列

输入样例

3
8 15 6

输出样例

2 2 2 3 5

数据范围

• $40\mathrm{\%}：n<=10,a_i<=100$
• $100\mathrm{\%}：n<=100,a_i<=10000$

---

代码参考

40分代码，辗转相除法+暴力

#include <iostream>
using namespace std;
int n, a[105];

int gcd(int a, int b) {
  while(b != 0) {
    int t = a % b;
    a = b;
    b = t;
  }
  return a;
}
int lcm(int a, int b) {
  return a/gcd(a, b)*b;
}

void factor(int x) {
  for (int i = 2; i * i <= x; i++) {
    while(x % i == 0) {
      cout << i << " ";
      x /= i;
    }
  }
  if (x > 1) {
    cout << x;
  }
  cout << endl;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int lcm_ma = a[1];
  for (int i = 2; i <= n; i++) {
    lcm_ma = lcm(lcm_ma, a[i]);
  }
  factor(lcm_ma);
  return 0;
}

40分代码，辗转相除法+分治算法

#include <iostream>
using namespace std;
int n, a[105];

int gcd(int a, int b) {
  while(b != 0) {
    int t = a % b;
    a = b;
    b = t;
  }
  return a;
}
long long lcm(long long a, long long b) {
  return a/gcd(a, b)*b;
}

int lcm_find(int left, int right) {
  if (left == right) {
    return a[left];
  }
  int mid = (left + right) / 2;
  int left_lcm = lcm_find(left, mid);
  int right_lcm = lcm_find(mid+1, right);
  return lcm(left_lcm, right_lcm);
}

void factor(long long x) {
  for (long long i = 2; i * i <= x; i++) {
    while(x % i == 0) {
      cout << i << " ";
      x /= i;
    }
  }
  if (x > 1) {
    cout << x;
  }
  cout << endl;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  long long lcm_ma = lcm_find(1, n);
  factor(lcm_ma);
  return 0;
}

算法优化，请阅读以下文档

质因数分解与 LCM 计算

先自己尝试写代码，然后再查看以下代码：

满分代码

#include <iostream>
#include <cmath>  // 用于sqrt函数
using namespace std;
int n,x,tong[10005];

// 求一个数的质因子
void factorize(int num) {
  for (int i = 2; i * i <= num; ++i) {
    int cnt_i = 0;
    while (num % i == 0) {
      cnt_i++;
      num /= i;  // 继续除以当前因子，直到不能再整除
    }
    if (tong[i] < cnt_i) tong[i] = cnt_i;
  }
  // 如果剩下的数大于1，说明它是质数
  if (num > 1 && tong[num] == 0) {
    tong[num] = 1;
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x;
    factorize(x);
  }
  // 输出所有的质因子
  for (int i = 2; i <= 10000; ++i) {
    while(tong[i]--) {
      cout << i << " ";
    }
  }
  cout << endl;
  return 0;
}

:::