原始问题:
13195的素数是5、7、13和29。
600851475143这个数字的最大素数是什么?
这是我在JS中的答案:
function largestPrimeFactor(n){
var i=2;
while (i<=n){
if (n%i == 0){
n/=i;
}else{
i++;
}
}
console.log(i);
}
var a = 600851475143;
largestPrimeFactor(a)
我花了几个小时试图弄清楚如何在Ruby中做到这一点,以下是我的想法,但我无法让它发挥作用:
def largestPrimeFactor (n)
i = 2
while i <= n
if n % i == 0
n /= i
i++
puts i
end
end
end
a = 600851475143
puts largestPrimeFactor(a)
如果我需要使用这段代码,下面并不是我将如何解决这个问题,但这是我将如何编写与您所拥有的最相似的解决方案。
我用了两种方法使它更容易使用。要输出答案(我认为你在另一个问题中遇到了困难(,你需要运行:
puts largest_prime_factor(600851475143)
这是代码:
def largest_prime_factor(input)
i = 1
while i < input
input /= i if (is_prime?(i) && input%i == 0)
i += 1
end
input
end
def is_prime?(num)
(2...num).each {|i| num%i == 0 ? false : true}
end
要回答您最初的问题,您所缺少的只是一个else
,而不是使用i++
,您应该使用i += 1
。
def largestPrimeFactor (n)
i = 2
while i <= n
if n % i == 0
n /= i
else
i += 1
end
end
end
然而,这段代码并不是很"ruby式",所以我将提供一些我可能会使用的实现。
没有必要计算这个,因为ruby已经有了确定素数的方法。只需要prime
,它是ruby标准库的一部分。
require 'prime'
def largestPrimeFactor(n)
primes, _ = n.prime_division.transpose
primes.max
end
largestPrimeFactor(13195) # => 29
largestPrimeFactor(600851475143) # => 6857
此方法(以及您的原始JS代码(的唯一缺点是不使用所谓的内存化,因此多次使用相当大的数字调用largestPrimeFactor
可能会导致计算浪费。我们可以通过使用我的解决方案的稍微复杂一点的版本来解决这个问题:
require 'prime'
def largestPrimeFactor(number)
@largest_prime_factor ||= {}.tap do |hash|
hash.default_proc = proc do |_, key|
hash[key] = begin
primes, _ = n.prime_division.transpose
primes.max
end
end
end[number]
end
largestPrimeFactor(13195) # => 29
largestPrimeFactor(600851475143) # => 6857
当使用benchmark
(也是ruby标准库的一部分(运行这些不同的实现时,您可以看到的巨大改进
user system total real
JS port 0.030000 0.000000 0.030000 ( 0.036535)
without memozation 0.020000 0.000000 0.020000 ( 0.017466)
with memozation 0.000000 0.000000 0.000000 ( 0.000199)