0

私はRubyに比較的慣れていませんが、言語に関しては十分に単純に思えます。私はRubyでEuler Projectに取り組んでおり、次の速度に大きな問題があります:

10 未満の素数の合計は 2 + 3 + 5 + 7 = 17 です。200 万未満のすべての素数の合計を求めます。

私のコード:

beginning_time = Time.now
(1..10000).each { |i| i }

def isPrime(num)
    factors = 0
    primecount = 1
    while primecount <= num
        if (num%primecount == 0)
            factors += 1
        end
        if (factors > 2)
            return false
        end
        primecount += 1
    end
    return true 
end

def make_sieve(num)
    sieve = Array.new(num)
    summation = 0
    for i in 1..num
            if(isPrime(i) == true)
                summation += i
                puts i
                for x in i..num
                    if x%i == 0
                    # Go through entire array and make all multiples of i False
                        sieve[x] = false
                    else
                        sieve[i] = true                     
                    end
                end
            else
                # If i is NOT prime, move to the next number. in the For Loop
                next
            end
    end
    puts summation
end

make_sieve(2000000)


end_time = Time.now
puts "Time elapsed #{(end_time - beginning_time)*1000} milliseconds"

私はふるいについて正しい考えを持っていると思いますが、何が起こっているのか、このプログラムの実行が非常に遅くなる手がかりがありません。20,000 で実行すると、約 15 秒かかります。これはまだ遅いように見えますが、2,000,000 を入力したときよりもはるかに高速に出力されます。

論理的または構文的に、またはその両方で間違った方法でこれを行っていますか?

4

2 に答える 2

2

あなたのisPrime()テストは素数で非常に遅いです。しかし、あなたはそれさえ必要としません。ふるい分けの鍵は、最初はすべての数字が素数としてマークされていることです。次に、素数ごとに、その倍数をすべてマークします。したがって、ふるいの特定のエントリに到達すると、それが素数であるかどうかtrue、つまり素数であるとマークさfalseれているか、合成（いくつかのより小さな素数の倍数）であるとマークされているかがすでにわかります。

プライムであることをテストする必要はまったくありません。

倍数を見つけるには、数えるだけです。5 の場合、それ以降は 5 番目のエントリです。7 - 各 7 日。%オペレーターでテストする必要はありません。すぐに設定するだけfalseです。true最初はすべての数値が に設定されていたので、どれも に設定する必要はありませんtrue。

于 2013-08-09T10:52:47.757 に答える
2

あなたは Ruby で JavaScript コードを書いているようで、Ruby をエレガントにする微妙な点が欠けています。Ruby Best Practicesのようなものを見てください。これは非常に軽い読み物ですが、別の言語の概念を押し付けるのではなく、Ruby のイディオムを使用することを扱っています。

前述のように、エラトステネスのふるいの要点は、リストからすべての合成数を削除し、素数だけを残すことです。各要素の素数をチェックする必要はありません。

これは Rubyish のソリューションです。約 1.5 秒で実行されます。N配列要素で数を表現するのは少し複雑なN-1ので(i+i+1 .. num).step(i+1)、(n * 2 .. num).step(n)

def make_sieve(num)

  sieve = Array.new(num, true)

  sieve.each_with_index do |is_prime, i|
    next if i == 0 or not is_prime
    (i+i+1 .. num).step(i+1) { |i| sieve[i] = false }
  end

  puts sieve.each_index.select { |i| sieve[i] }.map { |i| i+1 }.inject(:+)

end

make_sieve(2_000_000)

出力

142913828923
于 2013-08-09T12:31:56.113 に答える