Tamis d'Eratosthenes en Rubis

Question

Plutôt que de supprimer la version Ruby de cet algorithme du réseau, je voulais créer la mienne sur la base de sa description. ici . Cependant, je ne peux pas comprendre deux choses

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. Pourquoi ne pas itérer à la fin du tableau?
2. Selon la description dans le lien au-dessus de la boucle, la boucle doit être séparée lorsque la racine carrée du dernier élément du tableau est supérieure à la prime actuelle.

Je suis à peu près sûr que cela a quelque chose à voir avec l'opération de suppression qui modifie la longueur du tableau. Par exemple, ma fonction donne actuellement 2,3,5,7,9,10 lorsque j'entre n = 10, ce qui est évidemment incorrect. Avez-vous des suggestions sur la manière de modifier cela pour qu'il fonctionne comme prévu?

Answer 1

Ce qui suit semble fonctionner. J'ai sorti l'arithmétique en virgule flottante et le carré au lieu de l'enracinement carré. J'ai également remplacé la boucle de suppression par un "sélectionner". appeler.

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

Edit: Je pense avoir compris comment vous essayez de faire cela. Ce qui suit semble fonctionner et semble correspondre davantage à votre approche initiale.

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

L'implémentation est plus rapide à 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

Je pense que cela peut être amélioré légèrement ainsi:

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 grande partie à cause de l'initialisation plus rapide du tableau, je pense, mais c'est marginal. (J'ai ajouté #compact aux deux pour éliminer les nil s non désirés)

Answer 3

Il s'agit d'une implémentation assez simple du pseudocode d'article Wikipedia , en utilisant un tableau 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

Ceci est une référence pour ceux qui sont intéressés. Le code provient de de ce site .

Ce code utilise également Sieve of Eratosthenes.

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[
 Ceci est une référence pour ceux qui sont intéressés. Le code provient de  de ce site . 

 Ce code utilise également Sieve of Eratosthenes. 

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)


 Et voici  un autre . 

<*>.to_i]
end

Et voici un autre .

<*>

Answer 5

ou

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

Il y a peut-être un moyen d'utiliser l'injection ici, mais la première chose à faire me fait mal à la tête aujourd'hui.