寻找最小的质因数

Question

我正在尝试创建一个函数，该函数 return 是给定数字的最小质因数：

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) 应该 return 67 而不是 returns 1，这不应该发生，因为 1 应该从arrayOfFactors 在第 7 行期间，如 Prime.prime? 1 returns false

有时return没什么:

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 为假，它将使 "if" 失败并继续进行。尝试让你的数组从 3..sqrt(number)... 开始，这将排除 1，并且你已经确定数字是奇数，所以也省去 2，当然没有必要看任何高于平方根；（因为因子总是成对出现 a*b=n，其中 a 和 b 是因子；在平方根的情况下，a = b...在所有其他情况下，一个小于，另一个大于，平方根）。

此外，与其收集整个集合，不如考虑一个常规循环，该循环会在找到质因数的瞬间短路：如果您只想要最小的因数，为什么要找到所有因数；（例如对于 3333，您可以快速找出最小的质因数是 3，但需要执行更多步骤才能找到所有因数）。

寻找最小的质因数

Finding smallest prime factor

ruby

primes