Tamiz de eratóstenes en rubí

Question

En lugar de eliminar una versión Ruby de este algoritmo de la red, quería crear la mía en función de su descripción aquí . Sin embargo no puedo entender dos cosas

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. ¿Por qué no se itera hasta el final de la matriz?
2. De acuerdo con la descripción en el enlace de arriba, el bucle debe dividirse cuando el squareroot del último elemento en la matriz es mayor que el primo actual; el mío lo hace antes.

Estoy bastante seguro de que tiene algo que ver con la operación de eliminación que modifica la longitud de la matriz. Por ejemplo, mi función actualmente da 2,3,5,7,9,10 cuando ingreso n = 10, lo que obviamente no es correcto. ¿Alguna sugerencia sobre cómo puedo modificar esto para que funcione como se supone?

Answer 1

Lo siguiente parece funcionar. Saqué la aritmética de punto flotante y el cuadrado en lugar de la raíz cuadrada. También reemplacé el bucle de eliminación con un " seleccionar " llamada.

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

Edit: Creo que descubrí cómo intentas hacer esto. Lo siguiente parece funcionar y parece estar más en línea con su enfoque original.

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

Hay una implementación más rápida en 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

Creo que puede mejorarse un poco así:

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

... en gran parte debido a la inicialización más rápida de la matriz, creo, pero es marginal. (Agregué #compact a ambos para eliminar los nil no deseados)

Answer 3

Esta es una implementación bastante sencilla del pseudocódigo del artículo de Wikipedia , usando un 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

Esta es una referencia para aquellos que están interesados. El código es de este sitio .

Este código también usa Tamiz de Eratóstenes.

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[
 Esta es una referencia para aquellos que están interesados. El código es de  este sitio . 

 Este código también usa Tamiz de Eratóstenes. 

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)


 Y aquí está  otro . 

<*>.to_i]
end

Y aquí está otro .

<*>

Answer 5

o

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

Puede haber una forma de usar inyectar aquí, pero el tema del inicio me duele la cabeza hoy.