numeros - Tamiz de Eratóstenes en Ruby

numeros primos del 1 al 100

Question

En lugar de eliminar una versión de Ruby de este algoritmo de la red, quería crear la mía basándose en 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 itera hasta el final de la matriz?
2. De acuerdo con la descripción en el enlace de arriba, el bucle debería romperse cuando la raíz cuadrada del último elemento de la matriz sea mayor que la raíz primaria actual: la mina 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 rinde 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 debería?

Answer 1

Lo siguiente parece funcionar. Saqué la aritmética de punto flotante y cuadrado en lugar de enraizamiento cuadrado. También reemplacé el bucle de eliminación con una llamada "Seleccionar".

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

Editar: creo que descubrí cómo estás tratando de 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 se puede mejorar ligeramente 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. ( #compact a ambos para eliminar el nil no deseado)

Answer 3

Esta es una implementación bastante simple del pseudocódigo del artículo de Wikipedia , usando una matriz de bits.

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

o

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

Puede que haya una manera de usar la inyección aquí, pero la cosa de inicio me duele la cabeza hoy.

Answer 5

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

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

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

Y aquí hay otro .

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)