Sieb von Eratosthenes in Ruby

Question

Anstatt eine Ruby-Version dieses Algorithmus aus dem Netz Schaben Ich wollte meine eigene erstellen auf der Grundlage seiner Beschreibung hier . Allerdings kann ich nicht herausfinden, zwei Dinge

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. Warum es iterieren nicht bis zum Ende des Arrays?
2. Nach der Beschreibung in der Verbindung über der Schleife sollte aus gebrochen werden, wenn die Quadratwurzel des letzten Elements in der Anordnung ist größer als die aktuelle Prime - Mine dies tut vor.

Ich bin ziemlich sicher, dass es etwas mit dem Löschvorgang Modifizieren der Länge des Arrays zu tun. Zum Beispiel zur Zeit meine Funktion ergibt 2,3,5,7,9,10 wenn ich eintrete n = 10, das ist offensichtlich nicht korrekt. Alle Vorschläge, wie ich über Aenderungen dies gehen kann, damit es funktioniert, wie es soll?

Answer 1

Die folgende scheint zu funktionieren. Ich nahm die Gleitkomma-Arithmetik und Quadrat statt quadratisch Verwurzelung. I ersetzt auch die Löschschleife mit einem „wählen Sie“ Anruf.

while primes[index]**2 <= primes.last
      prime = primes[index]
      primes = primes.select { |x| x == prime || x%prime != 0 }
      index += 1
end

Edit: Ich glaube, ich herausgefunden, wie Sie versuchen, dies zu tun. Die folgende scheint zu funktionieren, und scheint mit Ihrem ursprünglichen Ansatz mehr im Einklang zu sein.

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

Answer 2

Es gibt eine schnellere Implementierung unter 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

Ich denke, es kann leicht auf diese Weise verbessert werden auf:

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

... vor allem wegen der schnelleren Array Initialisierung, denke ich, aber es ist marginal. (Ich habe #compact sowohl die unerwünschten nils zu beseitigen)

Answer 3

Dies ist eine ziemlich einfache Implementierung des Wikipedia-Artikel Pseudo-Code , mit einem Bit-Array.

#!/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

Answer 4

Dies ist eine Referenz für diejenigen, die interessiert sind. Der Code ist von dieser Seite .

Dieser Code verwendet Sieb des Eratosthenes auch.

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

Und hier ist ein anderes .

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)

Answer 5

oder

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

Es kann ein Weg sein, hier zu verwenden, spritzen, aber die Gründung Sache schmerzt meinen Kopf heute.