求一个数的质因数之和

假设这个数是 n，其质因数分解后为：

n = p1^k1 * p2^k2 * ... * pn^kn

其中，p1, p2, ..., pn 为质数，k1, k2, ..., kn 为正整数。

则该数的质因数之和为：

p1 + p2 + ... + pn

可以通过以下代码实现：

def prime_factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def prime_factor_sum(n):
    factors = prime_factorization(n)
    return sum(factors)

n = 123456789
print(prime_factor_sum(n))  # 输出结果为 431

其中，prime_factorization 函数用于对 n 进行质因数分解，prime_factor_sum 函数用于求质因数之和。

相关问题

C语言求一个数的质因数

在C语言中，求一个数的质因数通常涉及到遍历从2到该数平方根的所有整数，看它们是否能整除这个数。如果某个数能整除，那么它就是原数的一个质因数，同时将原数除以这个因子，并继续检查剩余部分，直到剩余数不再是之前因子的倍数。以下是简单的步骤：

#include <stdio.h>
#include <math.h> // 包含math库以便使用sqrt函数

void prime_factors(int num) {
    int i, factor = 2;
    while (num > 1) {
        if (num % factor == 0) { // 如果num能被factor整除
            printf("%d ", factor); // 输出当前的质因数
            num /= factor; // 更新num为余数，继续寻找下一个因数
        } else {
            factor++; // 如果不是，增加因子尝试下一位
        }
    }
}

int main() {
    int input_number;
    printf("请输入一个正整数：");
    scanf("%d", &input_number);
    printf("该数的质因数有：");
    prime_factors(input_number);
    return 0;
}

python编程求一个数的质因数

在Python中，求一个数的质因数可以通过循环和条件判断实现。以下是一个简单的算法示例：

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    # 如果n还有剩余，说明最后一个质因数大于sqrt(n)，直接添加
    if n > 1:
        factors.append(n)
    return factors

# 示例用法
number = int(input("请输入一个整数: "))
result = prime_factors(number)
print(f"{number}的质因数是: {result}")