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)