求最小素因子

Question

我试图创建一个函数，该函数返回给定数字的最小素数：

require 'prime'

def findSmallestPrimeFactor(number)
  return 2 if number.even?
  return number if Prime.prime? number
  arrayOfFactors = (1..number).collect { |n| n if number % n == 0 }.compact
  arrayOfFactors.each { |n| arrayOfFactors.pop(n) unless Prime.prime? n }
  return arrayOfFactors[0]
end

findSmallestPrimeFactor(13333)应该返回67，但是返回1，这不应该发生，因为在第7行中，1应该从arrayOfFactors中删除，Prime.prime? 1返回false

它有时什么也不回：

puts findSmallestPrimeFactor(13335) # => returns empty line

这个问题只有在处理一个不是偶数且不是素数的数字时才会发生，即忽略第4和第5行。

而且，当这件事完成后，我将通过它传递一些非常大的数字。对于较大的数字，是否有更短或更有效的方法来执行第6-8行？

Answer 1

由于您使用的是prime库，所以它有一个prime_division方法：

require 'prime'

13335.prime_division
# => [[3, 1], [5, 1], [7, 1], [127, 1]]
13335.prime_division[0][0]
# => 3

Answer 2

如果Prime.prime？是错误的1，它将失败的“如果”，并继续前进。尝试将数组从3..sqrt(数字).它不包括1，而且你已经确定了这个数字是奇数，所以也省去2，当然也没有必要看任何高于平方根的东西；(因为因子总是成对的a*b=n，其中a和b是因子；对于平方根，a=b.在所有其他情况下，一个小于平方根，另一个大于平方根)。

此外，与其收集整个集合，不如考虑一个规则的循环，即在它找到素数的那一刻就短路:如果您想要的是最小的因素，为什么要找到所有的因素；(例如，对于3333，您可以快速地找到最小的素数为3，但要找到所有的因素需要做更多的步骤)。