如何有效筛选出质数的选定范围? [英] How do I efficiently sieve through a selected range for prime numbers?

问题描述

我一直在解决 Project Euler 和Sphere Online Judge问题.在这个特定问题中，我必须找到两个给定数字内的所有素数.我有一个看起来很有前途的功能(基于筛网的筛子)，但它太慢了.有人可以发现导致我的功能减慢这么多的原因，并暗示如何解决该问题吗?此外，对于一般如何进行优化的一些评论(或指向此类评论/书/文章等的链接)也将不胜感激.

I've been working through Project Euler and Sphere Online Judge problems. In this particular problem, I have to find all the prime numbers within two given numbers. I have a function that looks promising (based on the Sieve of Eratosthenes), except it's too slow. Can someone spot what is slowing my function down so much, and hint at how I can fix it? Also, some comments about how to approach optimization in general (or links to such comments/books/articles etc,) would be greatly appreciated.

代码:

def ranged_sieve(l, b)
  primes = (l..b).to_a
  primes[0]=nil if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes[index] = nil if index
    end
  end
  primes.compact
end

推荐答案

我还没有完全了解，但是一个因素是，您要用nil替换primes中的某个值，然后使用compact -ing删除它们.这是浪费.只需直接使用delete_at进行操作，即可使其速度提高两倍以上:

I haven't looked fully, but one factor is that, you are replacing a certain value in primes with nil, and later compact-ing it to remove them. This is a waste. Just by doing that directly with delete_at makes it more than twice fast:

def ranged_sieve2(l, b)
  primes = (l..b).to_a
  primes.delete_at(0) if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes.delete_at(index) if index
    end
  end
  primes
end

ranged_sieve(1, 100) # => Took approx 8e-4 seconds on my computer
ranged_sieve2(1, 100) # => Took approx 3e-4 seconds on my computer

另一个需要改进的地方是，随着相关大小的增加，使用哈希比数组快得多.用哈希替换数组实现，可以得到以下信息:

Another point to improve is that, using a hash is much faster than array as the relevant size gets larger. Replacing your array implementation with a hash, you can get this:

def ranged_sieve3(l, b)
  primes = (l..b).inject({}){|h, i| h[i] = true; h}
  primes.delete(0)
  primes.delete(1)
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      primes.delete(stepped)
    end
  end
  primes.keys
end

使用range_sieve3(1, 100)进行此操作时，由于开销，它比range_sieve2(1, 100)慢.但是，随着数字的增加，优势变得显着.例如，我在计算机上得到以下结果:

When you do range_sieve3(1, 100) with this, it is slower than range_sieve2(1, 100) because of the overhead. But as you make the number larger, the superiority becomes salient. For example, I got this result on my computer:

ranged_sieve(1, 1000) # => Took 1e-01 secs
ranged_sieve2(1, 1000) # => Took 3e-02 secs
ranged_sieve3(1, 1000) # => Took 8e-04 secs

这篇关于如何有效筛选出质数的选定范围?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！