算数基本定理

文章目录

• 前言
• 算数基本定理
• 知识点
• 相关题目

前言

在学习Acwing c++蓝桥杯辅导课第八讲数论-Acwing 1295. X的因子链时有使用到算数基本定理，这里来记录下知识点。

当前文章已收录到博客文件目录索引：博客目录索引(持续更新)

算数基本定理

知识点

公式：N=P1^a1^ P2^a2^ P3^a3^ * ...... Pn^an^

算数基本定理，该定理说明：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。所有的整数都可以唯一分解成若干个质因子乘积的形式。

• 该乘积公式为：N=P1^a1^ P2^a2^ P3^a3^ * ...... Pn^an^，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。最早证明是由欧几里得给出的。

---

相关题目

Acwing 1295. X的因子链

根据该题题目说明要求：X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列。

举例严格递增情况：2    2*2    2*2*3   2*2*3*4

题目的说明完美的对准了算数基本定理：N=P1^a1^ P2^a2^ P3^a3^ * ...... Pn^an^，我们将一个数按照算数基本定理进行化解此时就可以得到序列的最大长度为a1 + a2 + a3 + a4 + … + an。