2370. 分解质因数
1000ms
256MB
简单
循环
简单数学
题目描述
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数。把一个合数用质因数相乘的形式表示出来，叫做分解质因数。例如：$12 = 2 \times 2 \times 3$，其质因数的个数为 3。
分解质因数的方法是先用这个合数的最小质因数去除，若商是质数则不再除下去；若商是合数则继续用最小质因数去除，直到最后得到的商是一个质数。
例如：合数 18 分解质因数，首先用最小质因数 2 去除，得商 9；继续用最小质因数 3 去除，得商 3（质数），停止分解。因此 18 的质因数为 2、3、3，质因数个数为 3。
现在给定一个正整数 $n$，请计算将其分解质因数后的质因数个数。
输入格式
- 输入一个正整数 $n$ ($1 \le n \le 10^6$)。
输出格式
- 输出一个整数，表示 $n$ 分解质因数后的质因数个数。如果 $n \le 1$，则输出 0。
样例 1
输入 (Input)
18
输出 (Output)
3
- 对于 $100\%$ 的数据：$1 \le n \le 10^6$。
- **算法提示**：
若要对 $n$ 进行质因数分解，无需从 2 循环到 $n$，只需循环到 $\sqrt{n}$ 即可：
1. 设当前试除数为 $i = 2$，当 $i \times i \le n$ 时执行循环。
2. 若 $n$ 能被 $i$ 整除，说明 $i$ 是 $n$ 的一个质因数。我们让计数器加 1，并将 $n$ 除以 $i$（即 $n = n / i$），重复该操作直到 $n$ 不能被 $i$ 整除为止。
3. 然后将 $i$ 递增，继续步骤 2。
4. 循环结束后，若剩下的 $n > 1$，说明此时的 $n$ 也是一个质因数（且它是大于原数平方根的唯一质因数），需要将计数器再加 1。
5. 这种方法的时间复杂度为 $O(\sqrt{n})$，在 $n \le 10^6$ 的情况下，最多只需运行 1000 次循环即可得出结果。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功