Ruby 质因数

Question

我看过用其他语言发布的解决方案，但没有 Ruby 所以我在这里问一下。

正在尝试找出 13195 的最大质因数。

我的代码如下

    # find out all numbers that divide without remainder into 13195

    array = []
    count = 2

    13195.times do 
        if 13195 % count == 0
            array.push(count)   
        end
        count += 1
    end



    #From those numbers that divide cleanly into 13195, find out which are prime aka can only be divided by themselves and 1

    new_count = 2
    primes = 0

    array.each do |x|
        while new_count < x 
            if x % new_count != 0
            else
                if x > primes
                primes = x
            end
            end
        new_count += 1
        end
    end

     puts primes

在我的第一个循环中，我用所有除以 13195 的数字填充了一个空数组，没有余数，从测试这段代码看来是有效的。

这是我的解决方案的第二部分，这是我每个陈述中的问题，有人可以指出我正确的方向吗？

Answer 1

您的第二个循环可以重写以执行预期的操作。

据我了解，您的目标是从 array 到 select，其中最大的素数元素（仅除以 1 和它本身）。换句话说，如果元素 x 不能被 2 和 x-1 之间的任何数字整除。

result = array.select {|x| not (2..x-1).any? {|i| x % i  == 0} }.max
#=> 29

目前，您的逻辑存在一些缺陷。它不会重置 new_count 的值，因此您会得到错误的结果。这是更正后的版本：

array.each do |x|
    is_prime = true
    while new_count < x 
        if x % new_count == 0
            is_prime = false
        end
        new_count += 1
    end
    new_count = 2
    primes = x if is_prime and x > primes
end

Answer 2

我建议你使用Prime#prime_division:

require 'prime'

def largest_prime_factor(n)
  Prime.prime_division(n).max_by(&:first).first
end

largest_prime_factor(13195)
  #=> 29

(1..1000).to_a.sample(15).sort.each {|n| puts "%3d: %3d" % [n, largest_prime_factor(n)]}
 61:  61
 80:   5
 88:  11
250:   5
304:  19
414:  23
514: 257
548: 137
679:  97
716: 179
754:  29
770:  11
906: 151
907: 907
968:  11

例如，

n = 13195
a = Prime.prime_division(n)
  #=> [[5, 1], [7, 1], [13, 1], [29, 1]] 
b = a.max_by(&:first)
  #=> [29, 1] 
b.first
  #=> 29

看来 prime_division 返回的数组元素是按素数递增的顺序排列的。如果能保证这一点，就可以写成：

Prime.prime_division(n).last.first

如果这些元素的顺序是特定于实现的，我使用了 max_by。

Answer 3

较短的版本：

require 'prime'
primes = Prime.each(13195).to_a
upper = primes.last

primes 将包含从 0 到 13195 的所有素数，显然是最后一个。

Answer 4

我将质数的限制设置为 100000（以避免像 600851475143 这样的大数计算几天 =)）

def prime_factors(n)
  prime_array = []    
  p = 2
  if n < 2
      return p
  end


  while p < n && p < 1000000
    if n % p == 0
      prime_array.push(p)
    end
  p +=1
  end

  primes = []

  prime_array.size.times do |i|
    if n > 1
      n = n / prime_array[i]
      primes.push(prime_array[i])
    end
  end
  return primes.last
end

#prime_factors(600851475143)
puts prime_factors(600851475143)

#prime_factors(13195)
puts prime_factors(13195)

Answer 5

另一种使用方式prime_division：

require 'prime'
(13195).prime_division.map(&:first).max
=> 29

Answer 6

不使用 Prime#prime_division 我们可以将问题分解成小部分。第一部分如果要编写一个方法来确定一个数字是否为质数，可以是这样的：

def prime?(num)

    if num < 2
        return false
    end
   (2...num).each do |ele|
      if num % ele == 0 
        return false
      end
   end
  return true
end

然后我们可以编写我们的主要方法，它要求一个数字的 prime_factors，例如：

def prime_factors(num)

prime_facts = []

(1..num).each do |i|
    if  num % i == 0 && prime?(i)
        prime_facts << i
    end
end
return prime_facts
end 

print prime_factors(24) #=> [2, 3]
puts
print prime_factors(60) #=> [2, 3, 5]
puts
print prime_factors(13195) # [5, 7, 13, 29]
puts

Ruby 质因数

Ruby Prime Factors

ruby

prime-factoring