求一个数的质因数之和

假设这个数是 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语言编写的程序，可以求出一个数的质因数之和：

#include <stdio.h>

int main() {
    int n, i, j, sum = 0;
    printf("请输入一个正整数：");
    scanf("%d", &n);
    
    // 从2开始循环，如果i是n的因数，则i一定是质数
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            // 判断i是否是质数
            for (j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    break;
                }
            }
            if (j > i / 2) {
                sum += i;
            }
            n /= i;
            i--;
        }
    }
    printf("质因数之和为：%d\n", sum);
    return 0;
}

程序的主要思路是从2开始循环到n，如果i是n的因数，则i一定是质数。然后再判断i是否是质数，如果是，则将i加入到质因数之和中。最后将n除以i，继续循环。

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;
}