我已经解决了一个代码战卡塔,但我不能提交它,因为我的代码需要太长时间很多人都有这个问题,但我们看不到解决办法问题是,生成素数花费的时间太长(超过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/