C++知识点总结(11)：质因子分解

2024-06-16 09:29| 来源: 网络整理| 查看: 265

一、质数和合数

质数

如果一个数除了 1 1 1 和本身，没有其他的因数，就是质数。

合数

如果一个数除了 1 1 1 和本身，还有其他的因数，就是合数。

小贴士

1 1 1 是一个例外，既不是质数，也不是合数。

二、求质数程序 #include using namespace std; int main() { int n; cin >> n; bool flag = true; // 默认 n 是质数 for (int i = 2; i flag = false; // 标注 n 不是质数 break; // 跳出循环，因为已经知道 n 不是质数了 } } } 三、分解质因数

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。

有一种快速的分解质因数的方法，叫做短除法。简单来说，短除法就是不断地用最小的质因数除以它本身。

步骤公式1 100 ÷ 2 = 50 100 \div 2 = 50 100÷2=502 50 ÷ 2 = 25 50 \div 2 = 25 50÷2=253 25 ÷ 5 = 5 25 \div 5 = 5 25÷5=54 5 ÷ 5 = 1 5 \div 5 = 1 5÷5=1 1. 初步推导 #include using namespace std; int main() { // 输入 int n; cin >> n; // 分解质因数 for (int i = 2; i cout while (n % i == 0) { cout while (n % i == 0) { cout while (n % i == 0) { cout // 输入 long long n; cin >> n; // 分解质因数 long long cnt; long long ans = 1; // 最终所有因数的个数 for (long long i = 2; i cnt++; n /= i; } ans *= (cnt+1); } // 特例 if (n > 1) { ans *= 2; } // 输出 cout if (n % i == 0) // n 是质因数的时候 { ans *= i; } while (n % i == 0) { n /= i; } } // 特例 if (n > 1) { ans *= n; // n 是一个新的质因数 } return 0; }

代码思路：

输入一个整数n通过一个for循环从2开始遍历到sqrt(n)，如果n可以被i整除，则表明i是n的一个质因数，将其乘到ans中通过一个while循环将n不断除以i，直到不能整除为止如果n大于1，则说明剩下的n是一个新的质因数，将其乘到ans中。六、数组游戏Ⅱ

题目描述

小明现在在进行一个数字游戏。在游戏中，给定一个初始数n，可以对数做以下操作任意次： 1、选择一个形如 x = p k x=p^k x=pk 且是该数是 n n n 的因数，其中 p p p 是一个质数， k ≥ 1 k \geq 1 k≥1，将 n ÷ x n \div x n÷x 。 2、每次选取的数需要互不相同。现在小明想知道，最多可以进行多少次这样的操作呢？

输入描述

输入共一行，包含一个整数 n n n （ 2 ≤ n ≤ 5 × 1 0 7 2 \leq n \leq 5 \times 10^7 2≤n≤5×107），表示初始数。

输出描述

输出一个整数，表示游戏过程中最多可以进行多少次操作。

样例1

输入

500

输出

样例解释

可以将 500 500 500 先除以 5 5 5 ，再除以 25 25 25 ，再除以 2 2 2 ，共执行 3 3 3 次。

参考代码

#include #include using namespace std; int main() { // 输入 int n; cin >> n; // 分解质因数 int cnt; int k; int ans = 0; for (int i = 2; i cnt++; n /= i; } while (k ans += 1; } cout 1 n>1，则说明剩下的 n n n 是一个新的质因数，将操作次数 + 1 +1 +137 a n s ans ans 即游戏过程中最多可以进行的操作次数

【本文地址】

公司简介

联系我们