15

このアルゴリズムの Ruby バージョンをネットからかき集めるのではなく、ここでの説明に基づいて独自のアルゴリズムを作成したいと考えました。しかし、私は2つのことを理解できません

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
  1. 配列の最後まで反復しないのはなぜですか?
  2. 上記のリンクの説明によると、配列内の最後の要素の平方根が現在の素数よりも大きい場合、ループを解除する必要があります-私の前にこれを行います。

配列の長さを変更する削除操作と関係があると確信しています。たとえば、私の関数は現在 n=10 を入力すると 2,3,5,7,9,10 を生成しますが、これは明らかに正しくありません。これを変更して、想定どおりに機能させる方法について何か提案はありますか?

4

5 に答える 5

17

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

...主に配列の初期化が高速であるためだと思いますが、限界です。#compact（不要な s を削除するために両方に追加しましたnil）

于 2009-01-11T12:57:56.693 に答える
5

以下はうまくいくようです。浮動小数点演算を取り出し、平方根の代わりに 2 乗しました。また、削除ループを「選択」呼び出しに置き換えました。

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
于 2008-10-27T23:50:22.497 に答える
3

これは、ビット配列を使用したウィキペディアの記事の疑似コードの非常に簡単な実装です。

#!/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
于 2012-03-05T09:13:05.593 に答える
1

興味のある方は参考にしてください。コードはこのサイトからのものです。

このコードでは、エラトステネスのふるいも使用しています。

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)
于 2014-05-11T02:02:10.773 に答える
0

また

x = []
Prime.each(123) do |p|
  x << p
end

ここで注入を使用する方法があるかもしれませんが、今日の開始のことで頭が痛いです。

于 2013-10-17T01:01:34.380 に答える