return 为字符串的质数分解

Question

我正在尝试解决以下编码挑战：

给定一个正数n > 1求n的质因数分解。结果将是具有以下形式的字符串：

"(p1xxn1)(p2xxn2)...(pkxxnk)"

如果 n(i) 为 1，则 p(i) 递增，n(i) 为空。

示例：n = 86240 应该 return "(2xx5)(5)(7xx2)(11)"

我相信我已经想出了如何找到一个数的质因数...我的问题是我不知道如何将它们转换成问题所需的形式（即一个字符串，其中 p( i) 递增顺序）。我试图将一个包含质因数的整数数组转换为某种包含因数 p 和 n 的元组数组，但我已经苦苦挣扎了几个小时，但毫无结果。

这是我目前的情况：

func factors(_ number: Int) -> String {
    var changedNumber = number
    var numberArr = [Int]()

    while changedNumber >= 2 {
        for i in 2...changedNumber {
            if changedNumber % i == 0 {
                numberArr.append(i)
                changedNumber /= i
                break
            }
        }
    }
}

任何见解或资源将不胜感激。

Answer 1

有很多方法可以解决这个问题。这是一个，超出我的想象：

为 Int 写一个扩展，具有以下功能

func isPrime() -> Bool

func nextPrime() -> Int.

首先检查输入的数字n是否为素数。如果是，return 结果为“(nxxx1)”，您就完成了。

定义一个 struct primeFactor:

struct PrimeFactor {
   let value: Int
   var count: Int
}

创建一个 PrimeFactors 数组。

func primeFactorsString(of value: String) -> String {
    var primeFactors = [PrimeFactor]()
    var currentPrime = 1
    var remainder = value
    guard !value.isPrime() else { return "(\(value)xx1)" }
    while remainder > 1 {
       currentPrime = currentPrime.nextPrime()
       if remainder % currentPrime == 0 {
          let newPrimeFactor = PrimeFactor(value: currentPrime, count: 1)
          remainder /= currentPrime
          while remainder % currentPrime == 0 {
              newPrimeFactor.count = newPrimeFactor.count + 1
              remainder /= currentPrime
          }
          primeFactors.append(newPrimeFactor)
       }
    }
    // Now loop through your array of primeFactors and build your output string.
    return primeFactors.map { "(\([=12=].value)xx\([=12=].count))".joined()

Answer 2

只需让您的函数对数字进行分组，然后在创建字符串时使用每个子集合计数：

func factors(_ number: Int) -> String {
    var changedNumber = number
    var numberArr: [[Int]] = []
    while changedNumber >= 2 {
        for i in 2...changedNumber {
            if changedNumber.isMultiple(of: i) {
                if numberArr.last?.last == i {
                    numberArr[numberArr.count-1].append(i)
                } else {
                    numberArr.append([i])
                }
                changedNumber /= i
                break
            }
        }
    }
    return numberArr.reduce(into: "") {
        if let last = .last {
            if .count == 1 {
               [=10=] += "(" + String(last) + ")"
            } else {
               [=10=] += "(" + String(last) + "xx\(.count))"
            }
        }
    }
}

print(factors(86240))   // (2xx5)(5)(7xx2)(11)

Answer 3

func factors(_ number: Int) -> String

我认为直接把这个return做成String是错误的。它违反了职责分离，并且难以重用。

想象一下，在使用此函数的代码库的其他地方，可能有一个函数试图将此字符串结果解析回数组中，以便以其他方式使用它。这听起来可能很荒谬，但我们在这里遇到的大量问题都是关于人们试图构建系统以接受来自其他系统的愚蠢输入，而他们应该改变这些输入！

以下是我的建议：

func primeFactorization(of value: Int) -> (factor: Int, exponent: Int) {
    ...
}

func format(_ primeFactors: [(factor: Int, exponent: Int)]) -> String {
    return primeFactors
        .map { [=10=].exponent == 1 ? "(\([=10=].factor))" : "(\([=10=].factor)xx\([=10=].exponent))" }
        .joined()

}

所以你可以这样做：

let factorization = primeFactorization(of: 86240)
// Which results in: [
//     (factor: 2, exponent: 5),
//     (factor: 2, exponent: 1),
//     (factor: 7, exponent: 2),
//     (factor: 11, exponent: 1),
// ]

// Which you can then format as this one question wants:
format(factorization) // => "(2xx5)(5)(7xx2)(11)"

为了加分，您可以将第一个函数泛化为 BinaryInteger 上的扩展，这样您就可以编写类似 86240.primeFactorization().

的内容

return 为字符串的质数分解

Prime factorization with return being a string

swift

string

algorithm

prime-factoring