ruby - 在 Ruby 中生成质数 (Codewars kata : Primes in numbers)

Question

我已经解决了一个 Codewars 套路，但我无法提交，因为我的代码耗时太长。很多人遇到过这个问题，但我们看不到解决方案。问题是，生成素数的时间太长了(超过12s)(我用一种方法生成素数)。

在我的电脑中，我可以要求 Prime 类，这就解决了问题。但是在Codewar中不能要求类Prime，因此，我的生成素数的方法太慢了。

有什么帮助吗？

require "pry"

def primeFactors(n)
  start_time = Time.now
  puts start_time
  # find prime numbers smaller than n

  nums = (2..(n-1)).to_a
  odd_nums = nums.select { |num| num.odd? }

  primes = odd_nums.select do |num|
    is_prime(num)
  end

  end_time = Time.now
  duration = end_time - start_time
  puts end_time

  # divide until mod is 1
  dividend = n
  res_primes = []

  while dividend > 1

    primes.each do |prime| # prime divisor
      new_dividend = dividend.to_f / prime
      remainder = dividend % prime
      if remainder.zero?
        dividend = new_dividend
        res_primes << prime
        break
      end
    end
  end

  freqs = {}
  res_primes.each do |res_prime|
    freqs[res_prime] = res_primes.count(res_prime)
  end

  res_string = []
  freqs.keys.each do |key|
    if freqs[key] == 1
      res_string << "(#{key})"
    else
      res_string << "(#{key}**#{freqs[key]})"
    end
  end

  res_string.join
end


def is_prime(n)
  (2..n/2).none?{|i| n % i == 0}
end

Answer 1

好吧，对于初学者来说，您实际上只需要测试 Math.sqrt(n).to_i + 1，它应该有助于获得更大的 n 值。

这是因为如果一个因素存在于 n = a * b 则要么

If a == b == sqrt(n) # 基本上是 sqrt 的定义

或

如果 a != b;一个 < 开方 (n); b > 开方(n)

如果 a 和 b 都小于 sqrt(n) 那么 a * b < n和如果 a 和 b 都大于 sqrt(n) 则 a * b > n

其次，这更复杂，您只需要将素数测试到该极限。我可以设想一个缓存素数的方案。

希望这对您有所帮助。