0

我对 Ruby 比较陌生，但就语言而言，它似乎很简单。我正在使用 Ruby 完成 Euler 项目，并且在以下方面遇到了很大的速度问题：

10 以下的素数之和为 2 + 3 + 5 + 7 = 17。求两百万以下的所有素数之和。

我的代码：

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 习语而不是强加另一种语言的概念。

如前所述，Eratosthenes 筛子的全部意义在于您只需从列表中删除所有复合数，只留下素数。无需检查每个元素的素数。

这是一个 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 回答