0

プロジェクトオイラーの問題12に取り組んでいます:

三角数のシーケンスは、自然数を加算することによって生成されます。したがって、7番目の三角数は1 + 2 + 3 + 4 + 5 + 6 + 7=28になります。最初の10項は次のようになります。

1、3、6、10、15、21、28、36、45、55、..。

最初の7つの三角数の要因をリストしましょう。

1:1
 3:1,3
 6:1,2,3,6
10:1,2,5,10
15:1,3,5,15
21:1,3,7,21
28:1,2,4,7,14,28

28は、5を超える約数を持つ最初の三角数であることがわかります。

500を超える約数を持つ最初の三角数の値は何ですか?

これが私が持っているものです:

require 'reusable'

# The idea here is that 2^n is the smallest number with n factors, 
# according to their definition, so it's a good place to start.
# It also happens to be a HUGE number, so I'm worried I'm thinking 
# about this wrong. Did 4999 instead of 5000, just to make sure 
# I didn't overshoot.
start = 2 * 4999

# The faster way to calculate the nth Triangle number
def nthTriangle(n)
 n * (n + 1) / 2
end

def answer(num)
    i = startingTriangle(num)
    while true
        triangle = i*(i+1)/2
        puts triangle
        factors = numFactors(triangle)
        return "#{triangle} is triangle number #{i}, with #{factors} factors." if factors > num
        i += 1
    end
end

# Basic reversal of the nthTriangle thing to figure
# out which n to start with in the answer function.
def startingTriangle(n)
    power = n - 2
    sqrt(power * 2).to_i - 1
end

puts answer(5000)

そして、その必要なファイル(オイラーの問題の束で再利用するメソッドを配置しようとしています):

def primesUpTo(n)
  nums = [0, 0] + (2..n).to_a
  (2..sqrt(n).to_i+1).each do |i|
    if nums[i].nonzero?
      (i**2..n).step(i) {|m| nums[m] = 0}
    end
  end
  nums.find_all {|m| m.nonzero?}
end

def prime?(n)
    test = primesUpTo(sqrt(n).to_i)
    test.each do |i|
        if n % i == 0
            return false
        end
    end
    true
end

# Just for faster, more intuitive (to me) array summing
def sum(array)
    array.inject(0) {|s, n| s + n }
end

# Ditto
def product(array)
    array.inject(1) {|p, n| p * n}
end

# I don't like typing the 'Math.'
def sqrt(n)
    Math.sqrt(n)
end

# Returns an array of arrays of the prime factors of num
# Form [[factor1, power1],[factor2, power2]]
# Ex: primeFactors(12) == [[2,2],[3,1]]
def primeFactors(n)
    array = []
    # 2 3 
    primesUpTo((n/2).to_i+1).select{ |i| n % i == 0 }.each do |p|
        pcount = 1
        n = n / p
        while n % p == 0
            pcount += 1
            n = n / p
        end
        array << [p, pcount]
    end
    array
end

# Returns the number of factors a number has
# INCLUDING both the number itself and 1
# ex: numFactors(28) = 6
def numFactors(n)
    return 2 if prime?(n)
    product = 1
    primeFactors(n).each do |i|
        product *= i[1] + 1
    end
    product
end

私の問題は、私のコードが本当に非常に遅いことです。開始番号の代わりに1から開始すると、200000(2 ^ 4999にはほど遠い)になるまでに1分+かかります。しかし、ライブラリの素数の解を破棄し、参照し続ける配列にすべての素数を追加することを除けば、これはほんの少しだけ速くなると思いますが、これをはるかに速くする方法は考えられません。そして、それははるかに高速である必要があります。

私はこれについてすべて間違っていると思っていますか?助言がありますか?

また、ライブラリメソッドの効率を改善する方法についての提案も役立ちます。これはおそらく何度も使用するでしょう。ゼロから作りたかったのでわかりましたが、非常に非効率的だと思います。

4

1 に答える 1

2

あなたのコードから:

ここでの考え方は、2^n が n 個の因数を持つ最小の数であるということです。

記載されている Project Euler タスクから:

28 は、約数が 5 を超える最初の三角形の数であることがわかります。

2^n が因数 n の最小数であると考える理由はわかりませんが、質問に示されている例は、28 より大きい 2^5 = 32 であるため、仮定が間違っていることを明確に証明しています。

私のソリューションは検索を 1 から開始し、かなり効率的です。素数は一切使いません。

補遺:完全を期すために、大きすぎる数から開始すること以外の大きな問題は、コメントで気づいて指摘したように、500 より大きい約数ではなく、5000 より大きい約数を検索することです。

于 2013-03-10T18:35:15.507 に答える