Ruby Prime Factors

Question

他の言語ではなくRubyで投稿されたソリューションを見たので、私はここで尋ねています。最大の素因数を見つけるためにしようと

13195.

私はせずに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 

を次のように私のコードですこのコードをテストして残ったものが動作しているようです。

私の解決策の2番目の部分は、それぞれの声明の中の問題です。誰かが正しい方向に向かうことができますか？

Answer 1

あなたの2番目のループは、何をするために書き直すことができます。

私は理解しているように、あなたの目標は、（1つだけと、それ自体で除算）プライムあるような要素の最大の、arrayから選択することです。それは2とx-1の間の任意の数で割り切れない場合は、他の言葉では、要素xが対象となります。

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を使用することをお勧め：ここでは、バージョン修正され

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 

、例えば

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 

prime_divisionによって返される配列の要素は、の順であることが表示されます素因数を増やす。それが保証された場合は、1だけ書くことができます：

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

I）は、（= 600851475143のような大きな数字の計算のカップル日のを避けるために）100000に

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)