我已经解决了一个代码战卡塔,但我不能提交它,因为我的代码需要太长时间很多人都有这个问题,但我们看不到解决办法问题是,生成素数花费的时间太长(超过12秒)(我用一种方法生成素数)。
在我的计算机中,我可以要求类素数,这就解决了问题但在码战中,不能要求类素数,因此,我生成素数的方法太慢了。
有什么帮助吗?

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

最佳答案

首先,你只需要测试Math.sqrt(n)到i+1就可以得到更大的n值。
这是因为如果存在一个因子,则n=a*b
如果a==b==sqrt(n)基本上是sqrt的defn

如果是!=b;asqrt(n)
如果a和b都小于sqrt(n),则a*b和
如果a和b都大于sqrt(n),则a*b>n
其次,这更复杂,你只需要测试素数到这个极限我可以设想一个缓存素数的方案。
希望这有帮助。

关于ruby - 在Ruby中生成质数(Codewars kata:质数),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/52971633/

10-11 23:22
查看更多