这是一个优秀的Ruby实现素数分解吗？

Question

我在汗学院做一些练习问题。当前的方法是素因式分解。我想出了这个：

require 'prime'

def prime_factorization(n, primes = nil)
  return [n] if Prime.prime? n

  primes ||= Prime.take_while { |p| p < n/2 }
  factorization = []
  prime = primes.detect { |p| n % p == 0 }
  factor = n / prime
  factorization << prime

  if Prime.prime? factor
    factorization << factor
  else
    factorization += prime_factorization factor, primes
  end

  factorization
end

这方面的基准是：

user system total real prime factorization of 75: 0.000000 0.000000 0.000000 ( 0.000129) prime factorization of 750: 0.000000 0.000000 0.000000 ( 0.000241) prime factorization of 4202: 0.000000 0.000000 0.000000 ( 0.000498) prime factorization of 39450: 0.010000 0.000000 0.010000 ( 0.003061) prime factorization of 460522: 0.050000 0.000000 0.050000 ( 0.057704)

• 这种方法的大O符号是什么？
• 从复杂度/性能上看，该算法与最优素因子算法相比如何？
• 递归是解决这个问题的好方法吗？
• 如何改进呢？
• 这是个愚蠢的问题？

Answer 1

重新发明车轮

考虑到您使用的是Prime类，有一个更简单的解决方案，它已经有一个Prime.prime_division()方法来完成几乎相同的任务。唯一的区别是输出格式:您的prime_factorization(360)将输出[2, 2, 2, 3, 3, 5]，而Prime.prime_division(360)将输出[[2, 3], [3, 2], [5, 1]]。这只是通过重复每个素数的次数来转换输出的问题。

require 'prime'

def prime_factorization(n)
  Prime.prime_division(n).flat_map { |factor, power| [factor] * power }
end

(感谢@Flambino和@tokland简化了转换。)

评论

你问了一些非常有趣的问题。

这种方法的大O复杂度根本就不容易分析。您可以调用诸如Prime.prime?()之类的方法，而这些方法反过来又利用了生成器。然后你也叫Prime.take_while()，Prime.prime?(factor)。除此之外，还有递归。不过，我要说的是，这种方法可能效率很低。

最初对prime?(n)的调用已经完成了一个类似于您的方法将执行的工作类型的试用部门。调用prime?完全是多余的-请参见下面的简化1。

对primes ||= Prime.take_while { |p| p < n / 2 }的调用也可能非常低效。例如，要计算prime_factorization(360)，您将要求它生成最多179的素数，即使不存在高于5的素数。

Ruby提供了一个Integer.divmod()函数，使您不必在确定了n / p之后立即重新计算n % p == 0。

当您递归时，您再次测试每一个素数，从2，3，5，…开始。相反，您希望能够通过测试成功的相同的主要因素来继续。

简化1

假设您是有意的重新发明车轮，您仍然可以通过以下几种方式改进您的方法：

• 消除对prime?的调用
• 将take_while移除以利于break，从而使早期终止工作
• 使用divmod
• 用循环替换递归
• 当你检测到这些因素时，只要是yield因素。让to_enum和to_a负责将结果附加到数组中。

def prime_factorization(n)
  def factor_generator(n)
    Prime.instance.each do |p|
      break if p > n
      begin
        div, mod = n.divmod(p)
        if mod == 0
          yield p
          n = div
        end
      end while mod == 0
    end
  end

  to_enum(:factor_generator, n).to_a
end

简化2

上面的实现仍然是低效的，因为Prime.instance.each中已经隐藏了原始性测试。为了避免代码和Prime类之间的重复工作，您应该能够测试没有明显组合的任何增加的数字序列。

def prime_factorization(n)
  def factor_generator(n)
    for prime_candidate in Prime::Generator23.new
      break if prime_candidate > n
      begin
        div, mod = n.divmod(prime_candidate)
        if mod == 0
          yield prime_candidate
          n = div
        end
      end while mod == 0
    end
  end

  to_enum(:factor_generator, n).to_a
end