如何在R语言中通过质因数分解法实现LCM计算？

问题解决思路 #

你已经能通过RcppAlgos::primeFactorize获取单个数字的质因数频率，接下来只需整合多个数字的分解结果，提取所有质数的最高次幂，即可生成指定格式的表达式并计算LCM数值。

完整实现代码 #

library(RcppAlgos)
library(dplyr)

find_lcm <- function(lcm_list) {
  # 处理空输入
  if (length(lcm_list) == 0) {
    stop("输入列表不能为空")
  }
  
  # 生成每个数字的质因数-次数命名向量（替代data.frame更易索引）
  prime_fact_list <- lapply(lcm_list, function(num) {
    prime_fact <- primeFactorize(num) %>% table() %>% as.data.frame()
    setNames(prime_fact$Freq, as.character(prime_fact$.))
  })
  
  # 收集所有出现过的唯一质数
  all_primes <- unique(unlist(lapply(prime_fact_list, names)))
  
  # 计算每个质数的最高次幂
  max_powers <- sapply(all_primes, function(p) {
    max(sapply(prime_fact_list, function(x) ifelse(p %in% names(x), x[p], 0)))
  })
  
  # 生成要求的表达式字符串（如"2^3 * 3^2"）
  lcm_expr <- paste0(all_primes, "^", max_powers, collapse = " * ")
  
  # 计算LCM的实际数值
  lcm_value <- prod(as.numeric(all_primes)^max_powers)
  
  # 返回包含表达式和数值的结果列表
  list(
    lcm_expression = lcm_expr,
    lcm_value = lcm_value
  )
}

使用示例 #

# 计算12、18、24的LCM
result <- find_lcm(c(12, 18, 24))

# 输出表达式
cat("LCM表达式：", result$lcm_expression, "\n")
# 输出：LCM表达式：2^3 * 3^2

# 输出数值
cat("LCM数值：", result$lcm_value, "\n")
# 输出：LCM数值：72

关键步骤说明 #

• 转换为命名向量：将质因数分解结果从data.frame转为命名向量，方便通过质数名称快速索引对应次数。
• 收集唯一质数：遍历所有分解结果的名称，提取所有出现过的质数。
• 获取最高次幂：对每个质数，检查所有数字的分解结果，取该质数出现的最大次数。
• 生成表达式：通过字符串拼接，将质数与最高次幂组合成质数^次数格式，再用*连接所有项。

内容的提问来源于stack exchange，提问作者Ramakrishna S