蓝桥杯第2155题质因数个数 C++ Java Python

本文主要是介绍蓝桥杯第2155题质因数个数 C++ Java Python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

思路和解题方法

目标是计算给定数 n 的质因数个数。可以使用了试除法来找到 n 的所有质因数

读取输入的数 n。
从 2 开始遍历到 sqrt(n)，对于每个数 i：
如果 n 能被 i 整除，则进行以下操作：
将 n 除以 i，直到 n 不能再被 i 整除。 *** 重点循环试除法
质因数个数加一。
如果 n 大于 1，表示 n 本身也是一个质因数，质因数个数再加一。
输出质因数个数。

复杂度:

时间复杂度:

对于每个数 i，试除法的时间复杂度为 O(sqrt(n))。

空间复杂度:

程序的空间复杂度取决于输入的数 n 和一个额外的变量，因此为 O(1)。

c++ 代码

#include<iostream>
using namespace std;using ll = long long;int main() {ll n;cin >> n;int ans = 0;// 从 2 开始遍历到 sqrt(n)for (ll i = 2; i * i <= n; i++) {// 如果 n 能被 i 整除，则进行以下操作if (n % i == 0) {// 将 n 除以 i，直到 n 不能再被 i 整除while (n % i == 0)n /= i;// 质因数个数加一ans++;}}// 如果 n 大于 1，表示 n 本身也是一个质因数，质因数个数再加一if (n > 1)ans++;// 输出质因数个数cout << ans << endl;return 0;
}

Java 版本（仅供参考）

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();int ans = 0;// 从 2 开始遍历到 sqrt(n)for (long i = 2; i * i <= n; i++) {// 如果 n 能被 i 整除，则进行以下操作if (n % i == 0) {// 将 n 除以 i，直到 n 不能再被 i 整除while (n % i == 0)n /= i;// 质因数个数加一ans++;}}// 如果 n 大于 1，表示 n 本身也是一个质因数，质因数个数再加一if (n > 1)ans++;// 输出质因数个数System.out.println(ans);}
}

Python 版本（仅供参考）

import mathn = int(input())
ans = 0
# 从 2 开始遍历到 sqrt(n)
for i in range(2, int(math.sqrt(n)) + 1):# 如果 n 能被 i 整除，则进行以下操作if n % i == 0:# 将 n 除以 i，直到 n 不能再被 i 整除while n % i == 0:n //= i# 质因数个数加一ans += 1# 如果 n 大于 1，表示 n 本身也是一个质因数，质因数个数再加一
if n > 1:ans += 1# 输出质因数个数
print(ans)

代码细节：

试除法找质因数： 使用试除法来找到给定数 n 的所有质因数。从 2 开始逐个试除，直到找到质因数为止。当找到一个质因数时，将 n 除以该质因数直到 n 不能再被该质因数整除。

质因数个数统计： 统计质因数的个数，包括重复的质因数。每次找到一个质因数后，质因数个数加一。

特殊情况处理： 需要特别注意 n 是否大于 1 的情况，如果大于 1，表示 n 本身也是一个质因数，质因数个数再加一。

循环边界： 在使用试除法时，循环的边界条件为 i * i <= n，这样可以确保在试除过程中不会漏掉质因数。