在Ruby中筛选Eratosthenes
而不是从网上抓取这个算法的Ruby版本，我想根据它的描述在这里创建我自己的。 但是我无法弄清楚两件事
def primeSieve(n) primes = Array.new for i in 0..n-2 primes[i] = i+2 end index = 0 while Math.sqrt(primes.last).ceil > primes[index] (primes[index] ** 2).step(primes.length - 1, primes[index]) {|x| x % primes[index] == 0 ? primes.delete(x) : ""} index += 1 end primes end - 为什么它不迭代到数组的末尾？
- 根据上面链接中的描述，当数组中最后一个元素的平方根大于当前素数时，应该打破循环 – 我之前做过这个。
我很确定它与修改数组长度的删除操作有关。 例如，当我输入n = 10时，我的函数当前产生2,3,5,7,9,10，这显然是不正确的。 关于我如何改变它以使它像它应该的那样工作的任何建议？
以下似乎有效。 我取出浮点算术并取平方而不是平方根。 我还用“select”调用替换了删除循环。
while primes[index]**2 <= primes.last prime = primes[index] primes = primes.select { |x| x == prime || x%prime != 0 } index += 1 end
编辑：我想我弄清楚你是怎么做的。 以下似乎有效，似乎更符合您的原始方法。
while Math.sqrt(primes.last).ceil >= primes[index] (primes[index] * 2).step(primes.last, primes[index]) do |x| primes.delete(x) end index += 1 end
http://www.scriptol.org上的实施速度更快：
def sieve_upto(top) sieve = [] for i in 2 .. top sieve[i] = i end for i in 2 .. Math.sqrt(top) next unless sieve[i] (i*i).step(top, i) do |j| sieve[j] = nil end end sieve.compact end
我认为可以稍微改进一下：
def better_sieve_upto(n) s = (0..n).to_a s[0] = s[1] = nil s.each do |p| next unless p break if p * p > n (p*p).step(n, p) { |m| s[m] = nil } end s.compact end
…主要是因为更快的arrays初始化，我认为，但它是边缘的。 （我添加了#compact来消除不必要的nil ）
这是使用位数组的维基百科文章伪代码的非常简单的实现。
#!/usr/bin/env ruby -w require 'rubygems' require 'bitarray' def eratosthenes(n) a = BitArray.new(n+1) (4..n).step(2) { |i| a[i] = 1 } (3..(Math.sqrt(n))).each { |i| if(a[i] == 0) ((i*i)..n).step(2*i) { |j| a[j] = 1 } end } a end def primes(n) primes = Array.new eratosthenes(n).each_with_index { |isPrime, idx| primes << idx if isPrime == 0 } primes[2..-1] end
这是有兴趣的人的参考。 代码来自此站点 。
此代码也使用了Sieve of Eratosthenes。
n = 1000000 ns = (n**0.5).to_i + 1 is_prime = [false, false] + [true]*(n-1) 2.upto(ns) do |i| next if !is_prime[i] (i*i).step(n, i) do |j| is_prime[j] = false end end count = 0 list = (0..n).map do |i| count += 1 if is_prime[i] count end while gets puts list[$_.to_i] end
这是另一个 。
def eratosthenes(n) nums = [nil, nil, *2..n] (2..Math.sqrt(n)).each do |i| (i**2..n).step(i){|m| nums[m] = nil} if nums[i] end nums.compact end p eratosthenes(100)
要么
x = [] Prime.each(123) do |p| x << p end
可能有一种方法可以在这里使用注射，但是今天的初始事情会让我头疼。