蓝桥杯第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 math

n = 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，这样可以确保在试除过程中不会漏掉质因数。